题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。现在要支持 $m$ 次操作，操作有两种：

• 1 x k：把 $a_x$ 加上 $k$（$k$ 可以为负数）；
• 2 x y：输出 $\sum\limits_{i=x}^{y}a_i$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行三个整数，第一个整数为 $1$ 或 $2$ 表示操作类型。

输出格式

对每个 2 操作输出一行一个整数，表示区间和。

输入输出样例 #1

输入 #1

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

输出 #1

14
16

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$|a_i|\le 10^6$，$|k|\le 10^6$，操作中出现的 $x,y$ 均满足 $1\le x\le y\le n$。