Processing math: 100%
Prefix sum - MarisaOJ: Marisa Online Judge

Prefix sum

Time limit: 500 ms
Memory limit: 256 MB

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.

Input

  • 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