Prefix Sum (Range Sum Query) - Classic Problems | Repovive

CLS29. Prefix Sum (Range Sum Query)

1s256 MB

Given an array of $n$ integers, answer $q$ queries. Each query gives two indices $l$ and $r$ , and asks for the sum of elements from index $l$ to $r$ (inclusive).

Constraints

$1 \le n, q \le 10^5$
$-10^9 \le a_i \le 10^9$
$1 \le l \le r \le n$

Input

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_q \quad r_q \end{array}

Output

\begin{array}{l} S_1 \\ S_2 \\ \vdots \\ S_q \end{array}

Samples

Input

Explanation

For this input, the required output is 6 9 15.

Output

6
9
15

Input

Explanation

For this input, the required output is 2 -1.

Output

2
-1

Input

Explanation

For this input, the required output is 10 20 30.

Output

10
20
30

Given an array of $n$ integers, answer $q$ queries. Each query gives two indices $l$ and $r$ , and asks for the sum of elements from index $l$ to $r$ (inclusive).

$1 \le n, q \le 10^5$
$-10^9 \le a_i \le 10^9$
$1 \le l \le r \le n$

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_q \quad r_q \end{array}

\begin{array}{l} S_1 \\ S_2 \\ \vdots \\ S_q \end{array}