题目描述

维护一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，处理 $m$ 个操作，每个操作为下列两种之一：

• 1 x k：令 $a_x \gets a_x + k$；
• 2 l r：输出区间和 $\sum_{i=l}^{r} a_i$。

输入格式

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

第二行 $n$ 个整数为序列初值。

接下来 $m$ 行，每行一个操作。

输出格式

对每个 2 l r 操作输出一行，表示对应区间和。

样例

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

6
16

数据范围

$1\le n,m\le 10^5$，$|a_i|\le 10^9$，$|k|\le 10^9$。

区间和可能超出 int，需使用 long long。