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 queries at his array,
, of
integers. The queries take the form
OI L_i S_i
, where his array will answer the first that satisfies
or
if no valid
exists (
denotes the sum of elements from the 1-indexed
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
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line will contain two integers, and
, the number of array elements and the number of queries, respectively.
The next line will contain integers,
, the elements of the array.
The next lines will contain one of the above queries,
and
, the start of the query and the minimum sum of the subarray.
Output Specification
Output lines with
, 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
Comments