Efficient Subarray Sum Queries

You are given an array of n integers and q queries. For each query, you need to calculate the sum of a sub-array defined by its starting and ending indices (1-indexed). Use an efficient algorithm to handle multiple queries.

To solve this problem, you can precompute a prefix sum array. The sum of elements from index l to r is given by:

\( S(l, r) = P[r] - P[l-1] \)

where \( P[i] \) is the prefix sum up to index \( i \).

inputFormat

The input is read from standard input (stdin) and has the following format:

• 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.
• Each of the next q lines contains two integers l and r separated by a space, representing the start and end indices (1-indexed) of the subarray.

outputFormat

For each query, output the sum of the subarray on a new line to standard output (stdout).

## sample

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

6
9
15

</p>