O. Prefix queries
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note the higher time limit than usual.

You are given an array $$$a$$$ of $$$n$$$ integers and $$$q$$$ queries to process.

Each query consists of three integers, $$$l$$$, $$$r$$$ and $$$x$$$, and indicates that each value of $$$a$$$ between $$$l$$$ and $$$r$$$, inclusive, is incremented by $$$x$$$. Note that the updates are not independent, so the increments persist for the following queries.

After each query, print the minimum $$$i$$$ that satisfies the following conditions:

  • $$$2 \leq i \leq n$$$.
  • $$$a_{1} + a_{2} + \ldots + a_{i - 1} \leq a_{i}$$$.
If there is no such $$$i$$$, print $$$-1$$$ instead.
Input

The first line contains two integers, $$$n$$$ and $$$q$$$, the size of the array and the number of queries, respectively. $$$(2 \leq n \leq 10^{6}; 1 \leq q \leq 10^{6})$$$.

The next line contains $$$n$$$ integers, $$$a_{1}a_{2}\ldots a_{n}$$$. $$$(-10^{9} \leq a_{i} \leq 10^{9})$$$.

The following $$$q$$$ lines will each contain three integers, $$$l$$$, $$$r$$$ and $$$x$$$. $$$(1 \leq l \leq r \leq n; 1 \leq x \leq 10^{9})$$$.

It is guaranteed that the sum of $$$(r - l + 1) \cdot x$$$ over all queries is never greater than $$$10^{18}$$$.

$$$-$$$

Testcases in the subtasks are numbered from $$$1−20$$$ with samples skipped.

For testcases $$$1-5$$$, $$$2 \le n \le 1000$$$ and $$$1 \le q \le 1000$$$.

The remaining testcases do not satisfy any additional constraints.

Output

For each query, output the minimum $$$i$$$ that satisfies the following conditions:

  • $$$2 \leq i \leq n$$$.
  • $$$a_{1} + a_{2} + \ldots + a_{i - 1} \leq a_{i}$$$.
If there is no such $$$i$$$, print $$$-1$$$ instead.
Examples
Input
6 5
2 -1 1 0 0 1
4 5 1
1 1 4
2 2 9
4 6 20
1 1 3
Output
3
-1
2
2
4
Input
5 10
9 -17 -6 1 -58
1 4 4
3 4 5
1 4 7
5 5 1
2 2 3
5 5 6
5 5 7
2 3 10
2 4 7
2 4 7
Output
4
3
-1
-1
-1
-1
-1
-1
-1
2
Note

Explanation of the first sample:

  • After the first query, the array $$$a$$$ looks like this: $$$[2,-1,1,1,1,1].$$$ The smallest $$$i$$$ which satisfies the condition is $$$3$$$, as $$$a_1 + a_2 \le a_3$$$.
  • After the second query, the array $$$a$$$ looks like this: $$$[6,-1,1,1,1,1].$$$ There is no $$$i$$$ which satisfies the constraints.
  • After the third query, the array $$$a$$$ looks like this: $$$[6,8,1,1,1,1].$$$ The smallest $$$i$$$ which satisfies the condition is $$$2$$$, as $$$a_1 \le a_2$$$.
  • After the fourth query, the array $$$a$$$ looks like this: $$$[6,8,1,21,21,21].$$$ The smallest $$$i$$$ which satisfies the condition is $$$2$$$, as $$$a_1 \le a_2$$$.
  • After the fifth query, the array $$$a$$$ looks like this: $$$[9,8,1,21,21,21].$$$ The smallest $$$i$$$ which satisfies the condition is $$$4$$$, as $$$a_1 + a_2 + a_3 \le a_4$$$.

$$$-$$$

Idea: Esomer

Preparation: Esomer

Ocurrences: Advanced 10