{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"During university, it is often necessary to rent classrooms. From departmental events to study group discussions, applications to the school for classroom rentals are required. Classrooms vary in size and function, and the identity of the person renting them also affects the rental procedures.\n\nFaced with a vast amount of information regarding classroom rentals, we naturally hope to solve this problem through programming.\n\nWe need to handle the classroom rental information for the next $n$ days, during which on the $i$ day the school has $r_i$ classrooms available for rent. There are a total of $m$ orders, each described by three positive integers: $d_j,s_j,t_j$, indicating that a certain renter needs to rent classrooms from the $s_j$ day to the $t_j$ day (including the $s_j$ day and the $t_j$ day), requiring $d_j$ classrooms each day.\n\nWe assume that renters have no requirements regarding the size or location of the classrooms. That is, for each order, we only need to provide $d_j$ classrooms each day, and it does not matter which specific classrooms they are or whether they are the same classrooms each day.\n\nThe principle of renting classrooms is first come, first served, meaning we need to allocate classrooms to each order in the order they were received. If during the allocation process we encounter an order that cannot be fully satisfied, we need to stop the allocation of classrooms and notify the current applicant to modify their order. Here, \"cannot be satisfied\" means that there are not enough classrooms available for at least one day from the $s_j$ day to the $t_j$ day, specifically fewer than $d_j$ classrooms.\n\nNow we need to determine whether there will be any orders that cannot be fully satisfied. If so, we need to notify which applicant needs to modify their order."}},{"title":"Input","value":{"format":"MD","content":"The first line contains two positive integers $n,m$, representing the number of days and the number of orders.\n\nThe second line contains $n$ positive integers, where the $i$-th number is $r_i$, indicating the number of classrooms available for rent on the $i$-th day.\n\nThe following $m$ lines each contain three positive integers $d_j,s_j,t_j$, indicating the number of classrooms rented, and the start and end days of the rental.\n\nEach pair of adjacent numbers is separated by a single space. Days and orders are numbered starting from $1$."}},{"title":"Output","value":{"format":"MD","content":"If all orders can be satisfied, output a single line containing one integer $0$. Otherwise (if an order cannot be fully satisfied),\n\noutput two lines: the first line outputs a negative integer $-1$, and the second line outputs the applicant number that needs to modify their order."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 \n2 5 4 3 \n2 1 3 \n3 2 4 \n4 2 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 \n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"【Input and Output Sample Explanation】\n\nAfter satisfying the $1 $-th order, the remaining number of classrooms on the $4 $-th day is $0,3,2,3$. The $2$-th order requires $ 3 $ classrooms every day from the $2 $-th day to the $4$-th day, while the remaining number of classrooms on the $3$-th day is $ 2$, thus it cannot be satisfied. Allocation stops, and the $2$-th applicant is notified to modify their order.\n\n【Data Range】\n\nFor 10% of the data, there are $1≤ n,m≤ 10$;\n\nFor 30% of the data, there are $1≤ n,m≤1000$;\n\nFor 70% of the data, there are $1 ≤ n,m ≤ 10^5$;\n\nFor 100% of the data, there are $1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n$.\n\n\nNOIP 2012 Improvement Group Day 2 Problem 2\n\n2022.2.20 Added a set of hack data"}}]}