Teemu has a bank account. On some days he deposits or withdraws money. Some days he doesn't do anything with the account

Now he wonders how much his balance has changed between the morning of day a and evening of day b

Input

The first line contains a two integer, n and q, the number of days and the number of queries, respectively.

The second line contains n integers, x_1, x_2, \ldots, x_n. If x_i \gt 0, Teemu deposited total of x_i units of money on i^{th} day. If x_i \lt 0, Teemu withdrew total of |x_i| units of money on i^{th} day. If x_i=0, Teemu didn't touch the account on i^{th} day.

Each next q lines contain two integers, a_j and b_j, the first and last days of query j.

Output

Output q lines, one for each query. The j^{th} line should contain a single integer, the amount of money that the balance has changed between the morning of day a_j (i.e. before any deposits or withdrawals on that day) and the evening of the day b_j (i.e. after all deposits and withdrawals on that day).

Limits

• The balance of the account is always non-negative, i.e. \ge 0, and at most 10^6
• -100 \le x_i \le 100
• 1 \le n, q \le 10^4

Example

Input:

6 10
10 -5 -5 100 50 -100
1 6
1 2
5 6
4 4
4 6
2 3
1 3
3 4
3 6
2 4

Output:

50
5
-50
100
50
-10
0
95
45
90

Explanation:
1^{st} query: In the beginning of the first day the balance is 0, and after the last day the balance is 50, hence the difference is 50.
2^{nd} query: In the beginning of the first day the balance is 0, and after the second day the balance is 5 (=10-5), hence the difference is 5.
3^{rd} query: In the beginning of the second last day the balance is 100, and after the last day the balance is 50, hence the difference is -50.
4^{th} query: In the beginning of the fourth day the balance is 0, and after the fourth day the balance is 100, hence the difference is 100.