Migrated from Lutece 2076 甲乙丙丁戊己庚辛壬癸

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出$N$个数，初始值全为$0$，有以下三种操作：

1.将第$x$个数增加$y$.

2.将第$x$个数变成$y$.

3.求第$x$个数到第$y$个数的和。

Input

第一行一个整数$N(1<=N<=100000)$，代表数的个数。

第二行一个整数$Q(1<=Q<=100000)$，代表询问的个数。

接下来$Q$行，每行第一个整数$op$.

如果$op=1$,输入$x,y$,表示将第$x$个数增加$y(1<=x<=N,1<=y<=10000)$.

如果$op=2$,输入$x,y$,表示将第$x$个数变成$y(1<=x<=N,1<=y<=10000)$.

如果$op=3$,输入$x,y$,表示求第$x$个数到第$y$个数的和$(1<=x<=y<=N)$。

Output

对于每次$3$号操作，一行输出答案。

Samples

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

1
6