时间限制：1秒　　内存限制：256M

---

【问题描述】

　　加工厂在未来 \(n\) 天内每天可以生产 \(a_i\) 份食品，食品的保质期为一天（即当天生产的食品只能当天提供给客户）。

　　共有 \(m\) 个订单，每个订单用三个正整数描述：\(d,l,r\)，表示某客户在第 \(l\) 天到第 \(r\) 天，每天需要 \(d\) 份食品。

　　工厂处理订单的规则是先到先得，也就是说要按照订单的先后顺序处理每个订单。这个过程中，如果遇到一个无法完全满足的订单，则停止处理，通知客户修改订单。这里的无法满足是指从第 \(l\) 天到第 \(r\) 天中至少有一天剩余食品数不足 \(d\) 份。

　　现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个客户修改订单。

【输入格式】

　　第一行包含两个正整数 \(n, m\)，表示天数和订单的数量，天数与订单均用从 1 开始的整数编号。
　　第二行包含 \(n\) 个正整数，其中第 \(i\) 个数为 \(a_i\)，表示第 \(i\) 天生产的食品数量。
　　接下来有 \(m\) 行，每行包含三个正整数：\(d,l,r\)，意义如题目描述。输入顺序就是订单的先后顺序

【输出格式】

　　输出一个整数，若所有订单都能得到满足，则输出 0，否则输出第一个需要需要修改订单的客户编号。

【输入输出样例】

　Input

5 4
5 4 6 2 3 
3 1 3
2 3 5
1 2 4
2 1 5

　Output

3

【输入输出样例1说明】

　　加工厂每天可提供的食品份数为：5 4 6 2 3，按先后顺序共有4个订单：
　　第 1 个订单：第 1 到 3 天中每天需要 3 份食品，满足后，5 天剩余的食品数分别为 2 1 3 2 3。
　　第 2 个订单：第 3 到 5 天中每天需要 2 份食品，满足后，5 天剩余的食品数分别为 2 1 1 0 1。
　　第 3 个订单：第 2 到 4 天中每天需要 1 份食品，显然第 4 天不能提供食品，所以需要通知第 3 个客户修改订单。

【数据说明】

　　对于 \(10\%\) 的数据，\(1 ≤ n,m ≤ 10\)
　　对于 \(30\%\) 的数据，\(1 ≤ n,m ≤ 1000\)
　　对于 \(70\%\) 的数据，\(1 ≤ n,m ≤ 10^5\)
　　对于 \(100\%\) 的数据，\(1 ≤ n,m ≤ 10^6，0 ≤ a_i ≤ 10^9，0 ≤ d ≤ 10^9，1 ≤ l ≤ r ≤ n\)

【来源】

　　Mr.he