题目描述

在城市交通管理中，有时需要临时关闭道路进行修整、清洁或施工。每条道路的关闭会影响通行的车辆，因此交通部门需要在一定时间范围内规划可用道路资源，确保道路能够满足所有车辆的通行需求。

我们需要处理接下来 $n$ 天的道路通行安排，其中第 $i$ 天城市中有 $r_i$ 条道路可供通行。共有 $m$ 份道路申请，每份申请用三个正整数描述，分别为 $v_j, s_j, t_j$，表示某个区域从第 $s_j$ 天到第 $t_j$ 天每天需要 $v_j$ 条道路供车辆通行（包括第 $s_j$ 天和第 $t_j$ 天）。

申请者对道路的具体位置没有要求。对于每份申请，只需要每天提供 $v_j$ 条道路，而具体是哪几条道路不做要求，且每天是否为同样的道路也无所谓。

道路分配的原则是按照申请的先后顺序依次处理每份申请。如果在处理某份申请时，无法在申请的时间段内完全满足车辆的道路需求，则需停止分配，并通知当前申请者修改申请。无法满足指的是在第 $s_j$ 天到第 $t_j$ 天中的至少一天，剩余的可通行道路数不足 $v_j$ 条。

现在，我们需要知道是否有申请者的需求无法完全满足。如果有，需要通知哪一个申请者修改他们的申请。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示天数和申请的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可供通行的道路数量。

接下来有 $m$ 行，每行包含三个正整数 $v_j, s_j, t_j$，表示某份申请的通行道路需求，以及道路需求的开始和结束天数。

每行相邻的两个数之间均用一个空格隔开。天数与申请均用从 $1$ 开始的整数编号。

输出格式

如果所有申请均可满足，则输出只有一行，包含一个整数 $0$。否则（有申请无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改申请的申请者编号。

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

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

-1
2

样例 1 解释

• 第 $1$ 份申请满足后，$4$ 天的可通行道路数分别为 $0,3,2,3$。
• 第 $2$ 份申请要求在第 $2$ 天到第 $4$ 天每天提供 $3$ 条道路，而第 $3$ 天的剩余道路数只有 $2$ 条，因此无法满足。

分配停止，需通知第 $2$ 个申请者修改申请。

其余样例

附件

数据范围

对于 $10\%$ 的数据，有 $1 ≤ n,m ≤ 10$

对于 $30\%$ 的数据，有 $1 ≤ n,m ≤ 1000$

对于 $70\%$ 的数据，有 $1 ≤ n,m ≤ 10^5$

对于 $100\%$ 的数据，有 $1 ≤ n,m ≤ 10^6,0 ≤ r_i,v_j≤ 10^9,1 ≤ s_j ≤ t_j ≤ n$。