Stone Heights Summation

You are given n stones arranged in a line, where the height of the i-th stone is given in an array. You are also provided with m queries, each of which asks for the total height of all the stones between positions a and b (inclusive). Your task is to process all queries efficiently.

The summation can be computed using prefix sums. Specifically, if we define the prefix sum \(P[i]\) as the sum of the first \(i\) stone heights, then the sum for the query \([a, b]\) is given by:

\(\text{Result} = P[b] - P[a-1]\)

Note that the stones are numbered starting from 1.

inputFormat

The input is given via stdin:

• The first line contains two integers n and m where n is the number of stones, and m is the number of queries.
• The second line contains n integers representing the heights of the stones.
• The next m lines each contain two integers a and b representing the inclusive indices of the query.

outputFormat

For each query, output the sum of the stone heights in the specified range on a new line to stdout.

## sample

6 3
4 2 3 7 8 6
1 3
2 5
4 6

9
20
21

</p>