Prefix Sums

Problem Description

Little J needs a program that can quickly compute the sum of any interval of a sequence. You have a try too!

Input Format

The first line contains two positive integers $n(1\le n \le 10^6)$ and $m(1\le m \le 10^6)$.

The second line contains $n$ int integers separated by single spaces.

The following $m$ lines each contain two positive integers $x,y$ separated by a single space, representing one query: what is the sum of the elements in the interval $[x,y]$?

Output Format

Output $m$ lines, each containing a single integer: the sum of the elements of the sequence over the corresponding interval $[x,y]$ (guaranteed to fit in a long long).

Sample Input

5 3
9 1 2 0 6
2 4
1 3
2 5

Sample Output

3
12
9

Hint

We will meet intervals very often from now on. Square brackets denote a closed interval that includes its endpoints, while round brackets denote an open interval that excludes them, e.g.

$[2,5]$ means $2, 3, 4, 5$;

$[2,5)$ means $2, 3, 4$.