Interval Sum Query

You are given a sequence of n positive integers \(a_1, a_2, \cdots, a_n\) and m queries. Each query is an interval \([l_i, r_i]\). For each query, compute the sum of the numbers in the interval.

More formally, for each query \([l, r]\), you need to calculate:

[ S = \sum_{i=l}^{r} a_i ]

Note that the indexes are 1-indexed.

inputFormat

The input begins with two integers n and m separated by a space, representing the number of elements in the sequence and the number of queries, respectively.

The second line contains n positive integers \(a_1, a_2, \cdots, a_n\) separated by spaces.

The following m lines each contain two integers \(l\) and \(r\) (1-indexed), representing the start and end of a query interval.

outputFormat

For each query, output a single number on a new line representing the sum of the interval \([l, r]\).

sample

3 2
1 2 3
1 2
2 3

3
5