Range Sum Query

You are given an array of integers and a series of queries. For each query, you need to compute the sum of a subarray from index L to R (inclusive). You can use prefix sums to efficiently compute these queries using the formula: $$S = prefix[R] - prefix[L-1]$$, where $$prefix[i] = a_1 + a_2 + \cdots + a_i$$.

Note that the array indices are 1-indexed.

inputFormat

The first line contains two integers N and Q, 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.

Each of the next Q lines contains two integers L and R which denote the range (inclusive) for which the sum is to be calculated.

outputFormat

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

## sample

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

6
14
15

</p>