Sum of Ranges

問題

$1$ 以上の整数 $N$ と、$0$ 以上の整数 $N$ 個からなる数列 $A = \{a_N\}$ が与えられる。

$Q$ 個のクエリ $(l_j, r_j)$ に対して、$a_{l_j}$ から $a_{r_j}$ までの和 $S_j$、すなわち、

を求めよ。

制約

• $1 \le N \le 10^5$
• $1 \le a_i \le 10^9 ~(1\le i\le N)$
• $1 \le Q \le 10^5$
• $1 \le l_j \le r_j \le N ~(1\le j\le Q)$

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 ... A_N
l_1 r_1
l_2 r_2
...
l_Q r_Q

出力

$Q$ 個のクエリについて、$S_j$ を $N$ 行で出力せよ。

入力例1

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

出力例1

6
9
15

$1$ 個目のクエリでは $1 + 2 + 3 = 6$ を出力します。
$2$ 個目のクエリでは $2 + 3 + 4 = 9$ を出力します。
$3$ 個目のクエリでは $1 + 2 + 3 + 4 + 5 = 15$ を出力します。

入力例2

8 3
31415 92653 58979 32384 62643 38327 95028 84197
1 3
2 7
1 8

出力例2

183047
380014
495626