Classroom Rental Order Processing

During university, classrooms are frequently rented for different activities. Each day, a certain number of classrooms is available. There are n days, and on day \(i\) there are \(r_i\) classrooms available for rental. There are m orders, each described by three positive integers \(d_j, s_j, t_j\), meaning that the renter requires \(d_j\) classrooms every day from day \(s_j\) to day \(t_j\) (inclusive).

The rental allocation is processed in the order the orders are received (first-come, first-served). For each order, if for any day in the range \([s_j, t_j]\) there are fewer than \(d_j\) classrooms available, then that order cannot be fully satisfied. In that case, processing stops and the applicant corresponding to this order should be notified (by outputting its order number, starting from 1). If all orders are fully satisfied, output 0.

Input Format: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers \(r_1, r_2, \dots, r_n\) representing the number of available classrooms on each day. The following \(m\) lines each contain three integers \(d_j, s_j, t_j\) describing an order.

Output Format: Output a single integer: the order number of the first order that cannot be fully allocated, or 0 if all orders are satisfied.

inputFormat

The input begins with two integers \(n\) and \(m\) separated by spaces, where \(n\) is the number of days and \(m\) is the number of orders. The next line contains \(n\) space-separated integers \(r_1, r_2, \dots, r_n\) representing the number of available classrooms on each day. Then \(m\) lines follow, each line contains three integers \(d_j\), \(s_j\), and \(t_j\) indicating that an order requests \(d_j\) classrooms from day \(s_j\) to day \(t_j\) (inclusive).

outputFormat

Print a single integer: the order number (starting from 1) of the first order that cannot be completely satisfied. If all orders can be satisfied, print 0.

sample

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

2