动态数据统计

题目描述

某数据系统需要维护一个长度为 (n) 的整数序列：

$a_1,a_2,\ldots,a_n$

初始时，序列中的所有元素均为 0。

系统需要依次处理 (m) 次操作。每次操作属于以下两种类型之一。

操作 1：增加数据

给出两个整数 (i) 和 (x)，执行：

a_i=a_i+x

也就是说，将序列中第 (i) 个元素增加 (x)。

操作格式为：

1 i x

操作 2：统计前缀

给出一个整数 (i)，计算：

$a_1+a_2+\cdots+a_i$

操作格式为：

2 i

请依次处理所有操作，并输出每次统计操作的结果。

---

输入格式

第一行输入两个整数：

n m

分别表示序列长度和操作次数。

接下来 (m) 行，每行描述一次操作，格式为以下两种之一：

1 i x

表示将第 (i) 个元素增加 (x)。

或者：

2 i

表示查询前 (i) 个元素的和。

---

输出格式

对于每个类型为 2 的操作，输出一行一个整数，表示查询结果。

---

数据范围

对于所有测试数据：

1 ≤ n,m ≤ 100000
1 ≤ i ≤ n
-10^9 ≤ x ≤ 10^9

保证所有查询结果均在 long long 的表示范围内。

---

样例输入

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

---

样例输出

8
7
12

---

样例解释

初始时：

a = 0, 0, 0, 0, 0

执行操作：

1 1 3

表示：

a_1=a_1+3

此时：

a = 3, 0, 0, 0, 0

接着执行：

1 3 5

表示：

$a_3=a_3+5$

此时：

a = 3, 0, 5, 0, 0

然后执行：

2 3

需要计算：

$a_1+a_2+a_3$

因此：

3+0+5=8

输出：

8

---

接着执行：

1 2 4

此时数组变为：

a = 3, 4, 5, 0, 0

执行：

2 2

计算：

$a_1+a_2=3+4=7$

输出：

7

最后执行：

2 5

计算：

$a_1+a_2+a_3+a_4+a_5$

即：

3+4+5+0+0=12

输出：

12

---