Range Sum Query with Prefix Sums

You are given an array of integers and a series of queries. Each query specifies two indices, \(l\) and \(r\) (1-indexed), and asks for the sum of the elements between these indices.

Using a prefix sum array, you can answer each query in \(O(1)\) time after an \(O(n)\) preprocessing step. The prefix sum array is defined as:

\[ prefix\_sums[i] = \sum_{j = 1}^{i} a_j \]

Thus, the answer to a query \((l, r)\) is given by:

\[ result = prefix\_sums[r] - prefix\_sums[l - 1] \]

Your task is to implement this logic. The input is read from standard input and the output should be printed to standard output.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\), denoting the number of elements in the array and the number of queries respectively.

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

Each of the following \(q\) lines contains two space-separated integers \(l\) and \(r\) (1-indexed) representing a query.

outputFormat

For each query, output the sum of the subarray from index \(l\) to \(r\) (inclusive) on a new line.

## sample

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

6
9
15

</p>