Description

bbq的工作是管理学校的社团活动，具体来说是为每个社团活动分配教室。要把有限的教室合理安排给这些社团，是不容易的。

每个社团活动用k, t1, t2来表示：该社团活动在第t1天～第t2天内需要k个教室（包括t1，t2）。

bbq总是按社团活动申请的先后顺序分配教室，如果某一天剩余的教室数量不够满足某社团的要求，则停止教室的分配。bbq需要告知该社团，他们的该次社团活动无法进行。

Input Format

每组输入数据第一行包括两个正整数n、m，为总天数和社团活动的总数量。

第二行包含n个正整数，其中第i个数为r​i​，表示第i天空教室的数量。

接下来有m行，每行为一个社团活动的信息，包含三个正整数k, t​1​, t​2。​（k, t1, t2如题目描述）。

规定：

天数与社团活动编号均用从1开始的整数编号。

$1≤n, m≤10​^6​，0≤ri≤10​^9​，0≤k≤10^9 ,1≤t​1​≤t​2≤n$。

Output Format

如果所有社团的申请均可满足，则输出0。

否则输出一个正整数，为需要bbq告知的活动无法进行的社团活动编号。

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4​

2​

Source

第一届ACM校赛 比赛