sumsecv

Task

You are given an array with $n$ natural number elements, indexed from $1$ to $n$, and $m$ pairs of indices $(i, j)$, with $1 \leq i < j \leq n$. For each pair $(i, j)$, determine the sum of the elements in the subarray determined by $i$ and $j$.

Input data

The first line will contain the numbers $n$ and $m$, and the second line will contain the $n$ elements of the vector. The next $m$ lines each contain a pair of indices $(i, j)$.

Output data

The output will contain the $m$ determined sums, each on another line.

Constraints and clarifications

• $1 \leq n, m \leq 100$;
• the elements of the vector will be less than $1000$.

Example 1

stdin

10 3
5 5 1 3 6 4 1 2 10 6 
5 8 
2 6 
6 10 

stdout

13
19
23