描述

给定一个长度为\(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