坤

题目背景
小T有一个长度为\(n\)的数列\(a_1,a_2,\cdots,a_n\)

接下来\(m\)次操作，每次操作形如：

"1 l r" 表示询问区间\([l,r]\)的\(a\)的和。
"2 l r x" 表示区间\([l,r]\)的每个\(a_i\)对\(x\)取模。
"3 k x" 表示把\(a_k\)赋值为\(x\)。
你能帮帮她么？

输入格式
第一行两个正整数\(n,m\)，分别表示序列长度和操作个数。

接下来一行\(n\)个整数，表示\(a_i\)。

接下来\(m\)行，每行一个操作。形式如题面所示。

输出格式
对于每个询问，输出一行表示答案。

样例1
input

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

output

8
5

样例2
input

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

output

49
15
23
1
9

限制与规定
对于\(30\%\)的数据，\(n,m\le10^3\)。

对于\(100\%\)的数据，\(n,m\le10^5,0\le a_i\le10^9\)。

时间限制：\(1s\)
空间限制：\(512MB\)

首先看到求和想到线段树，然后很自然地打了一个线段树暴力，每次取模时一个个取模，然后就获得了30分。
考虑怎么优化，发现如果一个区间的最大值都比\(x\)小，就不用再递归下去了。这样子就可以AC，我们来分析一下复杂度。
改数和求和都是线段树的基本操作，所以我么们看一下取模。对一个数取模一次，他要不不变，要不就减少一半。由于我们已经比较了最大值，那么这个数一定会减少一半。所以一个数w最多取模\(log w\)次。在寻找的过程中，我们每次保证最大值大于x，所以在区间中一定有需要数字要模，所以每次找一个数一定是\(log n\)次。总复杂度\(O(nlog^2n)\)

#include
const int N=1e5+5;
int n,m,x,op,l,r;
long long tr[N<<2],mx[N<<2];
inline int max(long long x,long long y)
{
	return x>1;
	if(mid>=x&&mx[o<<1]>=z)
		update(o<<1,l,mid,x,y,z);
	if(mid=z)
		update(o<<1|1,mid+1,r,x,y,z);
	tr[o]=tr[o<<1]+tr[o<<1|1],mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
void add(int o,int l,int r,int x,int y)
{
	if(l==r)
	{
		tr[o]=mx[o]=y;
		return;
	}
	int mid=l+r>>1;
	if(mid>=x)
		add(o<<1,l,mid,x,y);
	else
		add(o<<1|1,mid+1,r,x,y);
	tr[o]=tr[o<<1]+tr[o<<1|1],mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
long long query(int o,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return tr[o];
	int mid=l+r>>1;
	long long ret=0;
	if(mid>=x)
		ret+=query(o<<1,l,mid,x,y);
	if(mid