Treasure Distribution

You are given $n$ castles and $m$ knights. Each castle contains a certain amount of treasure. Every knight is assigned a segment represented by two integers $l$ and $r$, indicating the range of consecutive castles (1-indexed) that the knight can protect. Your task is to calculate the total amount of treasure each knight can protect, i.e. the sum of the treasures in the castles from index $l$ to $r$.

For example, if there are 5 castles with treasures [1, 3, 2, 5, 4] and a knight protects castles 1 to 3, then the total treasure for that knight is $1+3+2=6$.

inputFormat

The input is read from standard input (stdin). The first line contains two integers $n$ and $m$, representing the number of castles and knights respectively. The second line contains $n$ space-separated integers indicating the treasure in each castle. This is followed by $m$ lines where each line contains two integers $l$ and $r$, representing the segment (inclusive) that a knight can protect.

outputFormat

Output to standard output (stdout) exactly $m$ lines. The $i$-th line should contain a single integer representing the total treasure that the $i$-th knight can protect.## sample

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

6
10
15