分块只对#3，求调，必关

#include<bits/stdc++.h>
using namespace std;
int n,q,bl,t;
int head[1001],tail[1001];
long long a[1000001];
int cnt[1000001];
long long mx[1001];
int t1[1000001],t2[1001],t3[1001];
long long bk[1001];
long long add[1001];
long long calc(int i){
	if(t1[i]<=t2[cnt[i]]&&t3[cnt[i]]>t2[cnt[i]]){
		return bk[cnt[i]]+add[cnt[i]];
	}
	else if(t1[i]<=t2[cnt[i]]){
		return bk[cnt[i]];
	}
	else if(t3[cnt[i]]<t1[i])return a[i];
	else return a[i]+add[i];
}
void update(int i,int ii,int x){
	t1[i]=ii;
	if(t1[cnt[i]]>t2[cnt[i]])a[i]+=x;
	else a[i]=bk[cnt[i]]+x;
	mx[cnt[i]]=max(mx[cnt[i]],a[i]);
}
void update2(int i,int ii,int x){
	t1[i]=ii;
	a[i]=x;
	mx[cnt[i]]=max(mx[cnt[i]],(long long)x);
}
int main(){
	scanf("%d%d",&n,&q);
	bl=sqrt(n);
	t=n/bl;
	if(n%bl)t++;
	for(int i=1;i<=t;++i){
		head[i]=(i-1)*bl+1;
		tail[i]=i*bl;
	}
	tail[t]=n;
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		cnt[i]=(i-1)/bl+1;
		mx[cnt[i]]=max(mx[cnt[i]],(long long)a[i]);
		t1[i]=1;
	}
	for(int ii=1;ii<=q;++ii){
		int op,l,r;
		long long x;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lld",&x);
			if(cnt[l]==cnt[r]){
				for(int i=l;i<=r;++i){
					update2(i,ii,x);
				}
			}
			else{
				for(int i=cnt[l]+1;i<cnt[r];++i){
					t2[i]=ii;
					mx[i]=x;
					bk[i]=x;
				}
				for(int i=l;i<=tail[cnt[l]];++i){
					update2(i,ii,x);
				}
				for(int i=head[cnt[r]];i<=r;++i){
					update2(i,ii,x);
				}
			}
		}
		else if(op==2){
			scanf("%d",&x);
			if(cnt[l]==cnt[r]){
				for(int i=l;i<=r;++i){
					update(i,ii,x);
				}
			}
			else{
				for(int i=cnt[l]+1;i<cnt[r];++i){
					t3[i]=ii;
					add[i]+=x;
					mx[i]+=x;
				}
				for(int i=l;i<=tail[cnt[l]];++i){
					update(i,ii,x);
				}
				for(int i=head[cnt[r]];i<=r;++i){
					update(i,ii,x);
				}
			}
		}
		else{
			long long M=-1e9;
			if(cnt[l]==cnt[r]){
				for(int i=l;i<=r;++i){
					M=max(M,calc(i));
				}
			}
			else{
				for(int i=cnt[l]+1;i<cnt[r];++i){
					M=max(M,mx[i]);
				}
				for(int i=l;i<=tail[cnt[l]];++i){
					M=max(M,calc(i));
				}
				for(int i=head[cnt[r]];i<=r;++i){
					M=max(M,calc(i));
				}
				cout<<M<<endl;
			}
		}
	}
	return 0;
}