To stave off his boredom from not having a Communication Credit next term, Wesley decided to yell at his array (the closest thing to an intern).

He will yell $Q$ queries at his array, $A$, of $N$ integers. The queries take the form OI L_i S_i, where his array will answer the first $R$ that satisfies $S_i\le {\text{Sum}}_{[L_i,R_i]}$ or $N$ if no valid $R_i$ exists (${\text{Sum}}_{[L,R]}$ denotes the sum of elements from the 1-indexed $[L,R]$ in the array).

Since no one wants to be Wesley's intern, you are voluntold to be the array.

Can you answer these queries to prevent more yelling?

Constraints

$1\le N\le 2\times {10}^5$

$1\le Q\le 5\times {10}^5$

$1\le A_i\le 5\times {10}^3$

$1\le L_i\le N$

$1\le S_i\le {10}^9$

Subtask 1 [30%]

$1\le N,Q\le {10}^3$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain two integers, $N$ and $Q$, the number of array elements and the number of queries, respectively.

The next line will contain $N$ integers, $A_i$, the elements of the array.

The next $Q$ lines will contain one of the above queries, $L_i$ and $S_i$, the start of the query and the minimum sum of the subarray.

Output Specification

Output $Q$ lines with $R_i$, the answers to the queries.

Sample Input

6 6
1 5 3 2 1 7
OI 1 50
OI 1 19
OI 4 1
OI 1 12
OI 1 10
OI 2 8

Sample Output

6
6
4
5
4
3