Range Sum Queries

You are given a sequence of N integers and Q queries. In each query, a pair of integers L and R is provided, and your task is to compute the sum of all elements in the sequence from index L to index R (both inclusive). Indices are 1-indexed.

One efficient approach involves using prefix sums. Define the prefix sum array prefix such that:

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

Then the sum for a query [L, R] can be computed as:

$$ \text{sum} = prefix[R] - prefix[L-1] $$

This method ensures that each query is answered in constant time after an O(N) preprocessing step.

inputFormat

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

• The first line contains two integers N and Q representing the number of elements in the sequence and the number of queries.
• The second line contains N space-separated integers — the elements of the sequence.
• The following Q lines each contain two integers, L and R, representing a query.

outputFormat

For each query, output a single line containing the sum of the sequence's elements in the range from L to R (inclusive). The result should be printed to stdout.

## sample

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

9
12
15

</p>