009 - バイトテロユタカ2

前置き

この問題には3点分の部分点があります。

問題

ユタカくんは$N$日間バイトをし、$i$日目にはちょうど$A_i$枚の皿を割りました。
$Q$個の質問が与えられるので、それぞれについて答えを出力してください。
・$i$個目の質問の内容
$L_i$日目から$R_i$日目までの間、合計で何枚の皿を割りましたか？

入力

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

$N$ $Q$
$A_1$ $A_2$ ... $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
...
$L_Q$ $R_Q$

出力

$Q$行出力してください。
$i$行目には$i$個目の質問の答えを出力してください。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N, Q \leq 2×10^{5}$
• $1 \leq A_i \leq 2×10^{5} (1 \leq i \leq N)$
• $1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)$

部分点ケースについて追加で以下を満たす。
このケースに正解すると3点を得られる。

• $1 \leq N, Q \leq 100$

入出力例

入力例1

5 3
10 20 30 40 50
1 3
2 5
3 3

出力例1

60
140
30

入力例2

3 4
7 2 4
1 3
2 3
1 2
2 2

出力例2

13
6
9
2