Range Sum Query

You are given an array of integers and a series of queries. Each query asks for the sum of the elements in a subarray defined by two given indices, l and r (1-indexed). To solve the problem efficiently, you can precompute the prefix sums of the array.

The prefix sum is defined as follows:

$$ prefix[i] = prefix[i-1] + a_i $$

with the initial condition: $$ prefix[0] = 0 $$, where $$ a_i $$ is the i-th element of the array.

For each query, using the formula below, the sum of the subarray from l to r (inclusive) can be computed as:

$$ sum(l, r) = prefix[r] - prefix[l-1] $$

inputFormat

The input is given via standard input with the following format:

• The first line contains two integers, n and q, 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 space-separated integers, l and r (1-indexed), representing a query.

outputFormat

For each query, output a single line containing the sum of the array elements from index l to r (inclusive). The result for each query should be printed to standard output.

## sample

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

6
14
21

</p>