[NOIP2012]借教室
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题转译自 [NOIP2012 提高组] 借教室。
\hspace{15pt}学校每天有一定数量的教室可供租借。现在你获得了接下去 n 天的空闲教室信息，第 i 天有 r_i 个教室可供租借。 \hspace{15pt}系统一共有 m 份租借订单，已经按照申请时间从早到晚排序。第 j 份订单由一个三元组 \{d_j, s_j, t_j\} 描述，表示需要在第 s_j 天到第 t_j 天期间每天租借 d_j 个教室（包括第 s_j 天和第 t_j 天）。租借者对具体教室没有要求。
\hspace{15pt}按照先到先得的原则处理订单。如果某个订单在其租借期间有任何一天剩余教室数量不足，则需要通知该申请人修改订单，并停止处理后续订单。
\hspace{15pt}请判断是否存在无法满足的订单。如果存在，输出需要修改订单的申请人编号。

输入描述:

\hspace{15pt}第一行输入两个整数 n, m \left( 1 \leq n, m \leq 10^6 \right) 代表天数和订单的数量。
\hspace{15pt}第二行输入 n 个整数 r_1, r_2, \cdots, r_n \left( 0 \leq r_i \leq 10^9 \right) 代表每一天可用于租借的教室数量。
\hspace{15pt}此后 m 行，第 i 行输入三个整数 d_i, s_i, t_i \left( 0 \leq d_i \leq 10^9; 1 \leq s_i \leq t_i \leq n \right) 代表租借的教室数量、租借开始时间、租借结束时间。
\hspace{15pt}每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 1 开始的整数编号。

输出描述:

\hspace{15pt}如果订单无法完全满足，在一行上输出一个整数代表需要修改的订单申请人编号；否则，直接输出 0 。
\hspace{15pt}申请人编号即输入顺序，从 1 开始计数。
示例1

输入

复制 
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

输出

复制 
2

说明

\hspace{15pt}第一份订单满足后，这四天剩余的教室数为 \{0, 3, 2, 3\} 。
\hspace{15pt}第二份订单要求第二天到第四天每天提供 3 个教室，而第三天剩余的教室数为 2 ，因此无法满足。分配停止，通知第二个申请人修改订单。
示例2

输入

复制 
4 1
2 5 4 3
2 1 3

输出

复制 
0

备注: