Range Sum Query

You are given an integer array \(arr\) of size \(n\) and \(Q\) queries. Each query consists of two integers \(start\) and \(end\) (both inclusive). Your task is to compute the sum of the subarray \(arr[start \ldots end]\) for each query.

You can use the concept of prefix sums to answer each query in \(O(1)\) time after an \(O(n)\) preprocessing. The prefix sum array \(P\) is defined as:

[ P[i] = \sum_{j=0}^{i-1} arr[j], \quad 0 \leq i \leq n ]

Then, the sum for a query from index \(start\) to \(end\) can be computed as:

[ \text{sum} = P[end+1] - P[start] ]

Note that the indices in the queries are zero-based.

inputFormat

The first line contains two integers \(n\) and \(Q\) separated by a space, where \(n\) is the number of elements in the array and \(Q\) is the number of queries.

The second line contains \(n\) space-separated integers representing the array \(arr\).

Each of the following \(Q\) lines contains two integers \(start\) and \(end\), representing the starting and ending indices (inclusive) for a query.

outputFormat

For each query, output the sum of the elements from index \(start\) to index \(end\) on a new line.

## sample

5 2
1 2 3 4 5
0 2
1 4

6
14

</p>