Tree Heights Sum Query

You are given n trees with specified heights. Your task is to answer q queries, where each query asks you to compute the sum of heights of trees within a given 1-indexed range [l, r].

To solve this problem efficiently, you may precompute a prefix sum array where each element stores the cumulative sum of heights up to that index. Given this, the sum for a query from index l to r can be computed as:

$$S = \text{prefix}[r] - \text{prefix}[l-1]$$

Implement a program that reads the input from standard input and sends the results to standard output.

inputFormat

The input consists of the following parts:

• The first line contains two integers n and q, where n is the number of trees and q is the number of queries.
• The second line contains n integers representing the heights of the trees.
• Each of the following q lines contains two integers, l and r, representing a query for the sum of heights from the l-th tree to the r-th tree (inclusive).

outputFormat

For each query, output a single line containing the sum of tree heights in the given range.

## sample

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

7
9
10

</p>