题目描述

这是一道模板题。

给定一个长度为 $n$ 的整数数列 $a_1, a_2, \dots, a_n$，你需要依次进行 $q$ 个操作，操作包括以下两类：

1. 1 i x —— 将 $a_i$ 加上 $x$。
2. 2 l r —— 计算区间 $[l, r]$ 内所有元素的和，即 $\sum_{i=l}^{r} a_i$。

输入格式

第一行包含两个正整数 $n, q$，分别表示数列的长度和操作的个数（$1 \leq n, q \leq 2\times10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始数列（$1\le a_i\le 10^5$）。

接下来 $q$ 行，每行表示一个操作，格式如下：

• 1 i x（$1 \leq i \leq n, 1\le a_i\le 10^5$）：将 $a[i]$ 加上 $x$。
• 2 l r（$1 \leq l \leq r \leq n$）：输出区间 $[l, r]$ 内所有元素的和。

输出格式

对于每个 2 l r 操作，输出一个整数，表示所求的区间和，每个结果占一行。

样例输入1

3 2
1 2 3
1 2 0
2 1 3

样例输出1

6

样例输入2

5 5
1 4 3 5 6
1 2 0
2 1 3
2 3 4
1 5 3
2 1 5

样例输出2

8
8
22