누적 합

누적 합은 배열의 앞에서부터 원소의 합을 미리 계산하여 구간의 합을 빠르게 구하는 방법이다.

$N$개의 정수로 이루어진 배열 $A$가 있다. 배열의 인덱스는 1부터 시작한다.

$Q$개의 쿼리를 순서대로 처리하라.

각 쿼리에는 두 정수 $l$, $r$이 주어진다. $A_l+A_{l+1}+\cdots+A_r$을 출력한다.

첫 번째 줄에 배열의 크기 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 100\,000)$

두 번째 줄에 배열의 원소 $A_1,A_2,\cdots,A_N$이 주어진다. $(-10^9 \leq A_i \leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 두 정수 $l$, $r$이 주어진다. $(1 \leq l \leq r \leq N)$

각 쿼리의 결과를 한 줄에 하나씩 출력한다.