题目描述

给定一个长度为 $n$ 的数列，规定有两种操作，一是修改某个元素，二是求区间的连续和。

输入描述

输入数据第一行包含两个正整数 $n,m(n \le 1000000, m \le 1000000)$。

接下来一行， $n$ 个数字，表示数列的初识值。

接下来 $m$ 行询问，每行有三个正整数 $k,a,b(k=0 或 1,a,b ≤ n)$。$k=1$ 时表示将 $a$ 处数字加上 $b$，$k=2$ 时表示询问区间 $[a,b]$ 内所有数的和。

输出描述

对于每个询问输出对应的答案。

样例

样例输入 #1

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10
2 1 4
1 6 6
2 4 10
2 8 9
2 4 9
1 10 2
2 1 8
1 2 10
2 3 9
1 7 8
1 3 10
1 1 1
2 3 8
2 6 9
1 5 5
2 1 8
1 4 2
2 2 8
1 1 1

样例输出 #1

20
55
17
45
52
48
57
44
86
76