Compute Beauty Sums

You are given a row of N flowers and a list of Q queries. Each flower i has a beauty value b_i. For each query, given two integers L and R, you need to compute the sum of beauty values for the flowers from position L to position R (inclusive). In other words, for each query, compute:

$$ S = \sum_{i=L}^{R} b_i $$

It is guaranteed that the positions provided in the queries are 1-indexed and valid. Efficient computation is required as the numbers can be large.

inputFormat

The input is given via standard input (stdin) with the following format:

N Q
b1 b2 ... bN
L1 R1
L2 R2
...
LQ RQ

Here, N is the number of flowers, Q is the number of queries, and each query consists of two integers L and R.

outputFormat

Print Q lines to standard output (stdout). Each line should contain a single integer representing the sum of beauty values for the corresponding query.

## sample

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

16
29
7

</p>