Range Sum 1

You have a list with the integers $A_0, A_1, \dots , A_{N-1}$.

Your task is to answer $Q$ queries of the form “compute $A_L+A_{L+1}+\cdots +A_{R}$”, where $L$ and $R$ is specified per query.

Input

The first line of input contains two integers $N, Q$ ($1 \leq N \leq 3 \cdot 10^5$, $1 \leq Q \leq 10^5$).

The next line contains $N$ positive integers $A_0, A_1, \dots , A_{N-1}$ ($1 \leq A_i \leq 10^9$).

Afterwards, $Q$ lines follow, each containing two integers $L_{i},R_{i}$ ($0 \leq L_{i} \leq R_{i} \leq N-1$), the interval for each query.

Output

Output $Q$ rows, with the $i$:th one containing the answer to the $i$:th question.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of sample 1

In the first query, $L=0$ and $R=3$. Therefore, the answer is $A_0+A_1+A_2+A_3=1+4+3+1=9$.

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

9
5
4
7

3 1
1000000000 1000000000 1000000000
0 2

3000000000