Description

给出 n 个整数a[1],a[2],...,a[n] .

q 次操作，共有两种操作：

$1$ $l$ $r$ 查询 ${\textstyle \sum_{i=l}^{r}}a[i]$.

$2$ $p$ $w$ $a[p]\longleftarrow a[p]+w$

Format

Input

第一行有两个正整数 $n$ $q$ ， $n$ 表示数组长度， $q$ 表示操作次数.

第二行有 $n$ 个整数 $a[1],a[2],...,a[n]$.

接下来 $q$ 行，每行有三个整数，第一个是 $op$ 表示操作类型

若 $op=1$ 再输入 $l,r$ 表示查询 ${\textstyle \sum_{i=l}^{r}}a[i]$.

若 $op = 2$ 再输入 $p,w$ 表示令 $a[p]\longleftarrow a[p]+w$

$op\in \left \{1, 2 \right \}$ $1\le n,a[i],q,w\le 10^{5}$ $1\le l\le r\le n$ , $1\le p \le n$

Output

对于每次查询操作输出一个整数表示 ${\textstyle \sum_{i=l}^{r}}a[i]$.

Samples

5 2
1 2 3 4 5
2 1 2
1 1 2

5