累積和

長さ $N$ の数列$A=(A_0,A_1,...,A_{N-1})$ が入力されます。
続いて $Q$ 個のクエリが入力されます。各クエリでは $2$ つの整数 $i,j$ が与えられるので、$A_i+A_{i+1}+...+A_j$を求めて出力せよ。

入力

• $N$ $Q$
• $A_0,A_1,...,A_{N-1}$
• $i_1$ $j_1$
• $i_2$ $j_2$
• ...
• $i_Q$ $j_Q$

制約

• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• $-10^9 \le A_k \le 10^9$
• $0 \le i \le j < N$

• 出力

• 各クエリに対して区間$[i,j]$の総和を $1$ 行ずつ出力せよ。