题目描述

给定数列 $a_1,a_2,\cdots,a_n$，你需要进行 $q$ 个擦破自拍，操作有两类。

• 1 i x：给定 $i,x$，将 $a_i$ 加上 $x$
• 2 l r：求 $\sum\limits_{i=l}^r a_i$

输入格式

第一行包含两个正整数 $n,q$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示 $a_i$ 的初始值。

接下来 $q$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

• 1 i x 含义：将第 $i$ 个数加上 $x$
• 2 l r 含义：输出区间 $[l, r]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

3 2
1 2 3
1 2 0
2 1 3

6

提示

对于所有数据，$1\leq n,q\leq 10^6$，$|a_i|\leq 10^6$，$1\leq l\leq r\leq n$，$|x|\leq 10^6$。