rt,AC#1#3其他wa

#include <bits/stdc++.h>
#define inf LONG_LONG_MIN
#define ll long long
using namespace std;
const int maxn = 1e6+5;
int n , q , cnt , ls[maxn<<1] , rs[maxn<<1] , rt;
ll  t[maxn] , tag[maxn<<1] , tag2[maxn<<1];
inline ll input()
{
	char ch=getchar();int x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
inline void print(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
void PushUp(int p)
{
	t[p]=max(t[ls[p]] , t[rs[p]]);
}
void PushDown(int p)
{
	if (tag[p] != inf)
	{
		t[ls[p]]=t[p];
		t[rs[p]]=t[p];
		tag[ls[p]]=tag[p] + tag2[p];
		tag[rs[p]]=tag[p] + tag2[p];
		tag2[ls[p]]=0;
		tag2[rs[p]]=0;
		tag2[p]=0;
		tag[p]=inf;
		return;
	}
	t[ls[p]]+=tag2[p];
	t[rs[p]]+=tag2[p];
	tag2[ls[p]]+=tag2[p];
	tag2[rs[p]]+=tag2[p];
	return;
}
void Build(int &p , int l , int r)
{
	if (!p) p = ++cnt;
	tag[p]=inf;
	if (l == r)
	{
		int x = input();
		t[p]=x;
		return;
	}
	int mid = l + r >> 1;
	Build(ls[p] , l , mid);
	Build(rs[p] , mid + 1 , r);
	PushUp(p);
	return;
}
void Change(int &p , int l , int r , int L , int R , ll val)
{
	if (!p) p = ++cnt;
	if (L <= l && r <= R)
	{
		t[p]=val;
		tag[p]=val;
		tag2[p]=0;
		return;
	}
	PushDown(p);
	int mid = l + r >> 1;
	if (L <= mid) Change(ls[p] , l , mid , L , R , val);
	if (R > mid) Change(rs[p] , mid + 1 , r , L , R , val);
	PushUp(p);
	return;
}
void Add(int &p , int l , int r , int L , int R , ll val)
{
	if (!p) p = ++cnt;
	if (L <= l && r <= R)
	{
		t[p]+=val;
		if(tag[p] == inf)tag2[p]+=val;
		else tag[p]+=tag2[p];
		return;
	}
	PushDown(p);
	int mid = l + r >> 1;
	if (L <= mid) Add(ls[p] , l , mid , L , R , val);
	if (R > mid) Add(rs[p] , mid + 1 , r , L , R , val);
	PushUp(p);
	return;
}
ll Query(int &p , int l , int r , int L , int R)
{
	if (!p)return inf;
	if (L <= l && r <= R) return t[p];
	PushDown(p);
	int mid = l + r >> 1;
	ll res = inf;
	if (L <= mid) res = max(res , Query(ls[p] , l , mid , L , R));
	if (R > mid) res = max(res , Query(rs[p] , mid + 1 , r , L , R));
	return res;
}
int main ()
{
	n=input() , q=input();
	Build(rt , 1 , n);
	while(q--)
	{
		int op=input() , l=input() , r=input() , x;
		if (op == 1) x=input(),Change(rt , 1 , n , l , r , x);
		else if (op == 2) x=input(),Add(rt , 1 , n , l , r , x);
		else print(Query(rt , 1 , n , l , r)),putchar('\n');
	}
	return 0;
}