No submission language available for this problem.

题目背景

在一个旅游热门的海滨城市中，有一家名为"海景别墅"的高档度假旅馆。这家旅馆位于海边，拥有优美的海景和豪华的客房。由于其独特的地理位置和卓越的服务，"海景别墅"备受游客们的喜爱。

随着旅游旺季的来临，越来越多的游客涌入这座城市，纷纷想要预订"海景别墅"的客房。为了更好地管理客房预订流程，旅馆决定利用计算机编程来处理房间预订信息。

每天，旅馆会提供一份房间可供预订的情况表，包括各个类型房间的数量和可预订的日期范围。游客们需要根据自己的行程安排，提交预订申请表，包括入住日期、退房日期以及所需房间类型。

然而，由于旅游旺季的爆发，"海景别墅"的房间资源有限，旅馆管理层面临着房间调配和预订管理的挑战。为了更好地安排房间资源，他们决定利用编程技术来处理预订信息。

题面描述

在处理未来的 $n$ 天内的旅馆房间预订信息时，以下是具体的问题描述：

给定每一天 $i$ 旅馆提供的可供预订的房间数量 $r_i$，总共有 $m$ 份预订订单。每份订单由三个正整数描述，分别为 $d_j、s_j$ 和 $t_j$。其中，$d_j$ 表示某位预订者每天需要预订的房间数量，$s_j$ 和 $t_j$ 分别表示该预订者需要从第 $s_j$ 天到第 $t_j$ 天（包括这两天）预订房间。

在处理这些信息时，我们假设预订者对房间的类型和具体位置没有特殊要求。即每份订单中的 $d_j$个房间只需要满足数量要求即可，不需要考虑具体是哪些房间，以及每天是否需要相同的房间。

房间的分配原则是按照订单的先后顺序进行，即先到先得。如果在分配过程中遇到一份订单无法完全满足，我们需要停止分配，并通知当前预订者修改订单。无法完全满足的情况是指从第 $s_j$ 天到第 $t_j$ 天之间的某一天，剩余的房间数量不足 $d_j$个。

现在，我们的目标是判断是否存在无法完全满足的订单。如果存在这样的订单，我们需要通知哪位预订者修改订单以便更好地安排房间资源。

输入格式

第一行包含两个正整数 $n$，$m$，表示天数和订单的数量。 第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于预定的旅馆数量。 接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。 否则（订单无法完全满足）输出两行，第一行输出 -1，第二行输出需要修改订单的申请人编号。

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 \leq n, m \leq 10$； 对于 $30\%$ 的数据，有 $1 \leq n, m \leq 10^3$； 对于 $70\%$ 的数据，有 $1 \leq n, m \leq 10^5$； 对于 $100\%$ 的数据，有 $1 \leq n, m \leq 10^6$，$0 \leq r_i, d_j \leq 10^9$，$1 \leq s_j \leq t_j \leq n$。