p1253 20pts 玄关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[10010000],x,l,r;
struct node{
	int l,r,sum,mx,add;
}tree[40040000];
void build(int p,int l,int r){
	
	tree[p].l=l;
	tree[p].r=r;
	tree[p].mx=-1e18;
	if(l==r){
		tree[p].mx=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
}
void down(int p){
	if(tree[p].sum>-1e18){
		tree[p*2].mx=tree[p].sum;
		tree[p*2+1].mx=tree[p].sum;
		tree[p*2].sum=tree[p].sum;
		tree[p*2+1].sum=tree[p].sum;
		
		tree[p*2].add=0;
		tree[p].add=0;
    	tree[p*2+1].add=0;
        tree[p].sum=-1e18;
	}
	
		tree[p*2].add+=tree[p].add;
    tree[p*2+1].add+=tree[p].add;
	tree[p*2].mx+=tree[p].add;
	tree[p*2+1].mx+=tree[p].add;
	tree[p].add=0;
	tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);

	
}
void xg(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		tree[p].sum=k;
		tree[p].mx=k;
		tree[p].add=0;
		return;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) xg(p*2,l,r,k);
	if(mid<r) xg(p*2+1,l,r,k);
	tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
}

void update(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		tree[p].add+=k;
		tree[p].mx+=k;
		return;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) update(p*2,l,r,k);
	if(r>mid) update(p*2+1,l,r,k);
	tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
}
int ask(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r){
		return tree[p].mx;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	int ans=-1e18;
	if(l<=mid)ans=max(ask(p*2,l,r),ans);	
	if(r>mid)ans=max(ask(p*2+1,l,r),ans);
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	int op,x;
	while(q--){
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1){
			scanf("%lld",&x);
			xg(1,l,r,x);
		}
		if(op==2){
			scanf("%lld",&x);
			update(1,l,r,x);
		}
		if(op==3){
			printf("%lld \n",ask(1,l,r));
		}
	}
	return 0;
}