题目描述

给定一个长度为 $n$ 的数列，数列中默认初始值为 $0$ ，数列支持 $2$ 种操作：

1. 修改：将第 $a$ 个数加上值 $b$ ；
2. 查询：查询数列中区间为 $[a,b]$ （从第 $a$ 个数开始到第 $b$ 个数结束）的所有数的和。

读入 $m$ 次修改或者查询的指令，针对每次查询，请输出对应的区间和。

输入

输入数据第一行包含两个正整数 $n,m$ ($n≤10^5,m≤5 \times 10^5$)，接下来有 $m$ 行。

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

输出

对于每个询问输出对应的区间和。（本题读入的 $n$ 个数在 $[-2^{31},2^{31}-1]$ 的范围内，求出的区间和在 $[-2^{63},2^{63}-1]$ ）

样例

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

10
6
0
6
16
6
24
14
50
41