Range Sums

In this problem, you are given an array of integers and a number of queries. Each query provides two indices ( l ) and ( r ) (1-indexed), and your task is to compute the sum of the subarray from index ( l ) to index ( r ) inclusive. You are expected to utilize efficient techniques, such as prefix sums, to compute the result within the given time constraints.

For each query, if we define the prefix sum ( S[i] = \sum_{j=1}^{i} a_j ), then the answer for a query from ( l ) to ( r ) is given by ( S[r] - S[l-1] ).

inputFormat

The first line contains two integers ( n ) and ( q ), where ( n ) is the size of the array and ( q ) is the number of queries.

The second line contains ( n ) space-separated integers representing the elements of the array.

Each of the next ( q ) lines contains two integers ( l ) and ( r ), representing a query to calculate the sum of the subarray from index ( l ) to index ( r ) (1-indexed).

outputFormat

Output ( q ) lines, each containing a single integer: the sum of the subarray for each corresponding query.## sample

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

6
9
15