Efficient Subarray Sum Queries

You are given an array of integers and several queries. Each query asks for the sum of a subarray of the given array between indices L and R, both inclusive (1-indexed). To answer these queries efficiently, you should precompute the prefix sums of the array. The prefix sums array is defined as follows:

\( prefix\_sums[0] = 0 \) and \( prefix\_sums[i] = \sum_{j=1}^{i} array[j-1] \) for \( 1 \leq i \leq N \). Then, the sum of the subarray from L to R can be computed in \( O(1) \) time as:

\( sum = prefix\_sums[R] - prefix\_sums[L-1] \).

Your task is to process several queries using this method.

inputFormat

The input is given in the following format:

N Q
array[0] array[1] ... array[N-1]
L1 R1
L2 R2
... 
LQ RQ

where:

• N is the number of elements in the array.
• Q is the number of queries.
• array[i] are the integer elements of the array.
• Each query is represented by two integers L and R (1-indexed) indicating the subarray for which you need to compute the sum.

outputFormat

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

## sample

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

6
9
15

</p>