It's graphics time! For an assignment, you used separate methods to draw your ~N~ objects. However, it seems that Ready to Program cannot seemingly handle all your (totally) amazing drawings (without exploding and probably somehow cause the RtP equivalent of an IE on DMOJ)! You have given each of your objects a value, ~v_i~, which represents their style point. You also created ~Q~ queries to determine how many style points you will receive if you commented out every object except those in the range of the query. Out of these queries, determine the maximum number of style points you can score!

DISCLAIMER: Python CANNOT PASS (and now is no longer a submittable language)

Constraints

~1 \leq L_i < R_i \leq N~

Subtask 1 [20%]

~1 \leq N,Q \leq 10^3~

Subtask 2 [80%]

~1 \leq N,Q \leq 10^6~

~-10^5 \leq v_i \leq 10^5~

Input Specifications

The first line will contain two space-separated integers, ~N,Q~.

The next line will contain ~N~ space-separated integers, ~v_1,v_2,v_3,...v_n~, the style points of each object.

The next ~Q~ lines will contain two space-separated integers ~L_i,R_i~, describing the range ~[L_i,R_i]~ of the indices, inclusive.

Output Specifications

The first ~Q~ lines of your output should contain a single integer on each line, the sum of all the style points from ~L_i~ to ~R_i~.

The ~Q+1~th line should contain an integer ~M~, with ~1 \leq M \leq Q~, the query that has the highest style points. If there is a tie, output the query that appears first in the sample input.

Sample Input

3 2
5 6 -1
1 2
2 3

Sample Output

11
5
1

Sample Case Explanation

The first query contains the objects 5 and 6, which has a sum of 11. The second query contains the objects 6 and -1, which has a sum of 5. Since query 1 has a greater value than query 2, then the number on the last line is 1.