4WA，1TLE

#include<bits/stdc++.h>
#define N 2000009
#define M 2009
#define inf 1e15+9
using namespace std;
typedef long long ll;
ll n,m,L,a[N],b[N],bm[M],c[M],v1[M],v2[N];
inline void add(ll l,ll r,ll x){
	if(b[l]==b[r])
		for(int i=l;i<=r;i++){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
	else{
		for(int i=l;b[i]==b[l];i++){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
		for(int i=r;b[i]==b[r];i--){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
		for(int k=b[l]+1;k<=b[r]-1;k++) c[k]+=x,bm[k]+=x;
	}
	return;
}
inline void modi(ll l,ll r,ll x){
	if(b[l]==b[r])
		for(int i=l;i<=r;i++)
            v2[i]=v1[b[i]],a[i]=x;
	else{
		for(int i=l;b[i]==b[l];i++)
            v2[i]=v1[b[i]],a[i]=x;
		for(int i=r;b[i]==b[r];i--)
            v2[i]=v1[b[i]],a[i]=x;
		for(int k=b[l]+1;k<=b[r]-1;k++){
            v1[k]++;
            c[k]=x,bm[k]=x;
        }
	}
	return;
}
inline ll qw(ll l,ll r){
	ll ans=-inf;
	if(b[l]==b[r])
		for(ll i=l;i<=r;i++){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
	else{
		for(ll i=l;b[i]==b[l];i++){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
		for(ll i=r;b[i]==b[r];i--){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
		for(ll k=b[l]+1;k<=b[r]-1;k++) ans=max(ans,bm[k]);
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i];
	L=sqrt(n);
	for(ll i=1;i<=n;i++) b[i]=(i-1)/L+1;
	for(ll k=1;k<=b[n];k++){
		ll r=k*L;
		ll l=r-L+1;
		bm[k]=*max_element(a+l,a+r+1);
	}
	for(ll i=1;i<=m;i++){
		ll l,r,x,op;
		cin>>op>>l>>r;
		if(op==3) cout<<qw(l,r)<<endl;
        else{
            cin>>x;
            if(op==1) modi(l,r,x);
            else add(l,r,x);
        }
	}
	return 0;
}