Description

给定一个初始值全为 0 的长度为 n (1 <= n <=100000) 的序列(编号为 0,1,2,3 …… n-2,n-1) 进行 m (1 <= m <= 200000) 次操作,操作有两种 1 改变某个位置的数 2 询问某个区间的和 输出每次询问的值

Input

输入有多组数据 每组数据第一行为序列长度 n 和操作次数 m 接下来有 m 行,每行为一个操作,有三个数 b p q b 为 0 或 1 b 为 0 代表询问区间[p,q]的和 b 为 1 代表改变序号 p 的值,改变量为 q ,此时(-1000 <= q <= 1000)

Output

输出每次询问的值,每行一个

Sample Input

6 5 0 0 5 1 1 5 0 0 1 1 1 -2 0 0 2

Sample Output

0 5 3

Author

windy7926778