Interval Sum Queries

Given a sequence of n positive integers \(a_1, a_2, \cdots, a_n\) and m query intervals \([l_i, r_i]\), compute the sum of elements for each interval.

For each query, the answer is given by:

\[ S = \sum_{j=l}^{r} a_j \]

inputFormat

The first line contains two integers n and m, representing the number of elements in the sequence and the number of queries respectively.

The second line contains n positive integers: a1, a2, ..., an.

Each of the following m lines contains two integers l and r (1-indexed) that denote an interval for which you need to compute the sum.

outputFormat

For each query, output a single line containing the interval sum.

sample

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

6
14
3

</p>