描述

给定一个长度为$n$的序列,初始值为${1,2,3,......,n}$,编号为$1到n$
维护这个序列,可以进行单点修改,区间加法,区间求和

输入

第一行,一个整数$n$,表示序列的长度
第二行,一个整数$q$,表示操作次数
接下来的$q$行,每行若干个整数
若第一个整数为1,则后面接2个整数$x,y$,表示将序列的第$x$个数修改为$y$
若第一个整数为2,则后面接3个整数$l,r,s$,表示将序列的第$l$个到第$r$个数都加上$s$(即区间$[l,r]$都加上$s$)
若第一个整数为3,则后面接2个整数$l,r$,表示求当前序列的子区间$[l,r]$的所有数的和

输出

对于每个询问输出一行,一个整数,表示所求区间的和

输入样例

10
5
3 1 10
2 3 7 5
1 5 1
3 1 5
3 1 10

输出样例

55
21
71

数据范围和限制

对于50%的数据:$n\leq100000$
对于100%的数据:$1\leq n\leq 10^9,1\leq q\leq 200000,1\leq l\leq r\leq n,1\leq x\leq n,1\leq y\leq 10^9,1\leq s\leq 10000$
时间限制1s,空间限制256M