#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
	long long sum;
	int add1,maxa,maxb,add2,add4,add3;
	int smax,cnt;
}v[2000005];
int n,t;
int a[500005];
void push_add(int rt,int k){
	v[rt].add1+=k;
	v[rt].add3+=k;
	v[rt].add4=max(v[rt].add4,v[rt].add3);
	v[rt].add2=max(v[rt].add1,v[rt].add2);
	v[rt].sum+=(v[rt].r-v[rt].l+1)*k;
	v[rt].maxa+=k;
	
	if(v[rt].smax!=-2e9)v[rt].smax+=k;
}
void push_update(int rt,int k){
	v[rt].sum-=v[rt].cnt*(v[rt].maxa-k);
	v[rt].add3-=v[rt].maxa-k;
	v[rt].maxa=k;
}
void push_up(int rt){
	v[rt].sum=v[rt<<1].sum+v[rt<<1|1].sum;
	v[rt].maxb=max(v[rt<<1].maxb,v[rt<<1|1].maxb);
	v[rt].maxa=max(v[rt<<1].maxa,v[rt<<1|1].maxa);
	if(v[rt<<1].maxa==v[rt<<1|1].maxa){
		v[rt].cnt=v[rt<<1].cnt+v[rt<<1|1].cnt;
		v[rt].smax=max(v[rt<<1].smax,v[rt<<1|1].smax);
	}
	if(v[rt<<1].maxa<v[rt<<1|1].maxa){
		v[rt].cnt=v[rt<<1|1].cnt;
		v[rt].smax=max(v[rt<<1|1].smax,v[rt<<1].maxa);
	}
	if(v[rt<<1].maxa>v[rt<<1|1].maxa){
		v[rt].cnt=v[rt<<1].cnt;
		v[rt].smax=max(v[rt<<1].smax,v[rt<<1|1].maxa);
	}
}
void down(int a1,int a2,int a3,int a4,int rt){
	v[rt].sum+=a3*v[rt].cnt+a1*(v[rt].r-v[rt].l-v[rt].cnt+1);
	v[rt].maxb=max(v[rt].maxb,v[rt].maxa+a2);
	v[rt].maxa+=a3;
	if(v[rt].smax!=2e9)v[rt].smax+=a1;
	v[rt].add2=max(v[rt].add2,v[rt].add1+a2);
	v[rt].add4=max(v[rt].add4,v[rt].add3+a4);
	v[rt].add1+=a1;
	v[rt].add3+=a3; 
}
void push_down(int rt){
	int maxx=max(v[rt<<1].maxa,v[rt<<1|1].maxa);
	if(v[rt<<1].maxa==maxx)down(v[rt].add1,v[rt].add2,v[rt].add3,v[rt].add4,rt<<1);
	else down(v[rt].add1,v[rt].add2,v[rt].add1,v[rt].add2,rt<<1);
	if(v[rt<<1|1].maxa==maxx)down(v[rt].add1,v[rt].add2,v[rt].add3,v[rt].add4,rt<<1|1);
	else down(v[rt].add1,v[rt].add2,v[rt].add1,v[rt].add2,rt<<1|1);
	
	v[rt].add1=v[rt].add2=v[rt].add3=v[rt].add4=0;
}
void build(int rt,int l,int r){
	v[rt].l=l;
	v[rt].r=r;
	v[rt].add1=v[rt].add2=v[rt].add3=v[rt].add4=0;
	if(l==r){
		v[rt].cnt=1;
		v[rt].smax=-2e9;
		v[rt].maxb=v[rt].maxa=v[rt].sum=a[l];
		return;
	}
	//cout<<l<<" "<<r<<endl;
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}
void add(int rt,int l,int r,int k){
	if(l<=v[rt].l&&r>=v[rt].r){
		push_add(rt,k);
		return;
	}
	push_down(rt);
	int mid=(v[rt].l+v[rt].r)>>1;
	if(l<=mid)add(rt<<1,l,r,k);
	if(r>=mid+1)add(rt<<1|1,l,r,k);
	push_up(rt);
} 
void update(int rt,int l,int r,int k){
	if(v[rt].maxa<=k)return;
	if(l<=v[rt].l&&r>=v[rt].r&&v[rt].smax<=k){
		push_update(rt,k);
		return;
	}
	push_down(rt);
	int mid=(v[rt].l+v[rt].r)>>1;
	if(l<=mid)update(rt<<1,l,r,k);
	if(r>=mid+1)update(rt<<1|1,l,r,k);
	push_up(rt);
} 
int sigma(int rt,int l,int r){
	//cout<<v[rt].l<<" "<<v[rt].r<<endl;
	if(l<=v[rt].l&&r>=v[rt].r){
		return v[rt].sum;
	}
	int sum=0;
	push_down(rt);
	int mid=(v[rt].l+v[rt].r)>>1;
	if(l<=mid)sum+=sigma(rt<<1,l,r);
	if(r>=mid+1)sum+=sigma(rt<<1|1,l,r);
	return sum;
}
int maxize(int rt,int l,int r){
	if(l<=v[rt].l&&r>=v[rt].r){
		return v[rt].maxa;
	}
	int sum=-2e9;
	push_down(rt);
	int mid=(v[rt].l+v[rt].r)>>1;
	if(l<=mid)sum=max(sum,maxize(rt<<1,l,r));
	if(r>=mid+1)sum=max(sum,maxize(rt<<1|1,l,r));
	return sum;
}
int himax(int rt,int l,int r){
	if(l<=v[rt].l&&r>=v[rt].r){
		return v[rt].maxb;
	}
	int sum=-2e9;
	push_down(rt);
	int mid=(v[rt].l+v[rt].r)>>1;
	if(l<=mid)sum=max(sum,himax(rt<<1,l,r));
	if(r>=mid+1)sum=max(sum,himax(rt<<1|1,l,r));
	return sum;
}
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(t--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int l,r,k;
			scanf("%d%d%d",&l,&r,&k);
			add(1,l,r,k);
		}else if(op==2){
			int l,r,v;
			scanf("%d%d%d",&l,&r,&v);
			update(1,l,r,v);
		}else if(op==3){
			int l,r,k;
			scanf("%d%d",&l,&r);
			cout<<sigma(1,l,r)<<endl;
		}else if(op==4){
			int l,r;
			scanf("%d%d",&l,&r);
			cout<<maxize(1,l,r)<<endl;
		}else{
			int l,r,k;
			scanf("%d%d",&l,&r);
			cout<<himax(1,l,r)<<endl;
		}
	}
}