题目描述

输入有两种指令：

“$1\ i\ x$” 表示 a[i]=a[i]+x

“$2\ l\ r$” 表示求 $\sum\limits_{i=l}^r a_i$

输入格式

第一行输入 $n,q$ 第二行输入初始的 $a_1\dots a_n$ 后面 $q$ 行，每行一个指令

输出格式

$q$ 行每行一个正整数，表示答案

样例

3 2
1 2 3
1 2 0
2 1 3

6

数据范围

$n,q\le 10^6, \{a\}\in [-1000000, 1000000]$