Range Sum Query

You are given an array of N integers and Q queries. For each query, you are given two indices L and R (1-indexed) and need to compute the sum of the elements from index L to R in the array.

To solve the problem efficiently, you can use a prefix sum array. The prefix sum array P is defined by:

\(P[i] = \sum_{j=1}^{i} A[j]\)

Then, the sum for a query from L to R can be computed as:

\(\text{Sum}(L,R) = P[R] - P[L-1]\)

Read the input from stdin and write the answers for each query to stdout, one per line.

inputFormat

The first line contains two integers N and Q, representing the number of elements in the array and the number of queries.

The second line contains N integers, the elements of the array.

The next Q lines each contain two integers L and R (1-indexed), representing a query.

outputFormat

For each query, output a single line containing the sum of the elements from index L to R.

## sample

5 3
1 2 3 4 5
1 3
2 4
1 5

6
9
15

</p>