# Static Range Sum

AC一覧

## Problem Statement問題文

You are given a non-negative integer sequence $A = (a_0, a_1, \ldots, a_{N-1})$ with the length $N$. Process the following $Q$ queries in order:

• You are given integers $l_i$ and $r_i$. Print $\sum_{k=l_i}^{r_i-1} a_k$.

• 整数 $l_i, r_i$ が与えられるので、$\sum_{k=l_i}^{r_i-1} a_k$ を出力する。

## Constraints制約

• $1 \leq N \leq 500{,}000$
• $1 \leq Q \leq 500{,}000$
• $0 \leq a_i \leq 10^{9}$
• $0 \leq l_i < r_i \leq N$

## Input入力

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


## Sampleサンプル

### # 1

5 5
1 10 100 1000 10000
2 3
0 3
2 5
3 4
0 5

100
111
11100
1000
11111


Timelimit: 5 secs

Before submitting, please confirm terms and conditions