Range Sum Query

You are given an array of N integers and Q queries. Each query consists of two indices L and R and your task is to compute the sum of the subarray from index L to R (inclusive).

To solve the problem efficiently, you can precompute the prefix sums. The prefix sum array P is defined as:

[ P[i] = \sum_{j=0}^{i-1} a_j,\quad \text{for } i \ge 1, \quad \text{with } P[0] = 0. ]

Then, the sum of the subarray from L to R can be computed in constant time as:

[ \text{sum}(L, R) = P[R+1] - P[L]. ]

Implement a program that reads the input, processes the queries using this technique, and prints the result for each query on a new line.

inputFormat

The first line contains two integers N and Q separated by a space, representing the number of elements in the array and the number of queries respectively.

The second line contains N space-separated integers representing the array elements.

Each of the next Q lines contains two integers L and R indicating a query, where 0 ≤ L ≤ R < N.

outputFormat

For each query, output the computed sum of the subarray from index L to R on a new line.

## sample

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

6
9
12

</p>