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