You are given an integers array A of n elements and q queries, each of the form (l,r), calculate the sum Al+Al+1+…+Ar.
- The first line contains 2 integers n,q.
- The second line contains n integers Ai.
- Each line of the next q lines contains 2 integers l,r, a query.
Output
- Print q lines, the results of q queries.
Constraints
- 1≤n,q≤105.
- 1≤Ai≤109.
Example
Input:
5 3
1 3 -2 3 4
2 3
1 4
3 5
Output:
1
5
5