Sum of Ranges

以上の整数 と、 以上の整数 個からなる数列 が与えられる。

個のクエリ に対して、 から までの和 、すなわち、

を求めよ。

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

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

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

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

6
9
15

個目のクエリでは を出力します。
個目のクエリでは を出力します。
個目のクエリでは を出力します。

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

183047
380014
495626