在大学期间，经常需要租借教室。
大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。
教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息，其中第i天学校有riri个教室可供租借。
共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tjdj,sj,tj，表示某租借者需要从第sjsj天到第tjtj天租借教室（包括第sjsj天和第tjtj天），每天需要租借djdj个教室。
我们假定，租借者对教室的大小、地点没有要求。
即对于每份订单，我们只需要每天提供djdj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。
这里的无法满足指从第sjsj天到第tjtj天中有至少一天剩余的教室数量不足djdj个。
现在我们需要知道，是否会有订单无法完全满足。
如果有，需要通知哪一个申请人修改订单。
输入格式
第一行包含两个正整数n,m，表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为riri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj,sj,tjdj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从1开始的整数编号。
输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数0。
否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。
数据范围
1≤n,m≤1061≤n,m≤106,
0≤ri,dj≤1090≤ri,dj≤109,
1≤sj≤tj≤n1≤sj≤tj≤n
输入样例：
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例：
-1
2
package main
import (
"fmt"
)
var n , m int
var b = make([]int, 1000010)
var a = make([]int, 1000010)
var order = make([][]int, 1000010)
func check( mid int) bool {
for i := 1 ; i <= n ; i ++ {
b[i] = a[i] - a[i - 1]
}
for i := 1 ; i <= mid; i ++ {
b[order[i][1]] -= order[i][0]
b[order[i][2] + 1] += order[i][0]
}
// fmt.Println(b[:n+1])
for i:= 1; i <= n; i ++ {
b[i] += b[i - 1]
if b[i] < 0 {
return true
}
}
return false
}
// 差分
func main (){
fmt.Scanf("%d %d\n", &n, &m)
for i := 1 ; i <= n ; i ++ {
fmt.Scanf("%d", &a[i])
}
for j := 1; j <= m ; j ++{
var d , s, t int
fmt.Scanf("\n%d %d %d", &d, &s, &t)
order[j] = []int{d, s, t}
}
// fmt.Println(a, order)
// dj,sj,tj
l := 0
r := m
if !check(r) {
fmt.Println("0")
}else {
for l < r {
mid := r + l >> 1
if check(mid) {
r = mid
} else {
l = mid + 1
}
}
fmt.Println("-1")
fmt.Println(r)
}
}