정적 구간 합

길이가 $N$인 음이 아닌 정수 수열 $A = (a_0, a_1, \ldots, a_{N-1})$이 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리한다:

• 정수 $l_i$와 $r_i$가 주어진다. $\sum_{k=l_i}^{r_i-1} a_k$를 출력한다.

제약 조건

• $1 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $0 \leq a_i \leq 1000000000$
• $0 \leq l_i < r_i \leq N$

$N$ $Q$
$a_0$ $a_1$ $\ldots$ $a_{N-1}$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$

정수 $l_i$와 $r_i$가 주어진다. $\sum_{k=l_i}^{r_i-1} a_k$를 출력한다.