Sum Query on Array

You are given an array \(A\) of length \(N\) and \(Q\) queries. For each query, you need to compute the sum of a subarray from the \(L^{th}\) element to the \(R^{th}\) element. The indices are 1-indexed.

More formally, for each query with integers \(L\) and \(R\), compute the sum:

\( S = \sum_{i=L}^{R} A[i] \)

It is recommended to use a prefix sum array to answer the queries efficiently. The prefix sum \(P\) is defined as:

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

Then, the answer for a query \((L, R)\) can be computed as:

\( S = P[R] - P[L-1] \)

Implement a program for this task that reads input from standard input and writes output to standard output.

inputFormat

The input is given in the following format:

N Q
A[1] A[2] ... A[N]
L1 R1
L2 R2
... 
LQ RQ

Where:

• \(N\) is the size of the array.
• \(Q\) is the number of queries.
• The second line contains \(N\) integers representing the array \(A\).
• Each of the next \(Q\) lines contains two integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output a single integer that is the sum of the subarray from index \(L\) to \(R\). Each answer should be printed on a new line.

## sample

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

6
9
15

</p>