Prefix Sum

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ and $m$ queries.

Each query gives two numbers $l, r$, and asks for the value of $a_l + a_{l+1} + \dots + a_r$.

Input Format

The first line contains two integers $n, m$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

The following $m$ lines each contain two integers $l, r$.

Output Format

Output $m$ lines, each containing an integer: the answer.

Sample Input

5 5
7 6 4 7 4
2 5
1 3
3 5
1 2
2 4

Sample Output

21
17
15
13
17

Constraints

For $100\%$ of the data, $1 \leq n, m \leq 10^5, 1 \leq a_i \leq 10^9, 1 \le l \le r \le n$.