#include<cstdio>
#include<algorithm>
#define N 2000005
#define int long long 
#define inf 2000005
#define m (l+r)>>1
#define lc p*2
#define rc p*2+1
#define debug printf("debug")
using namespace std;
int n,mm;
inline int read(){
	int ans=0,sym=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')sym=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
	return ans*sym;
}
struct linetree{
	int l,r,maxa,se,maxb,cnt;
	int sum;
	int add_a,add_a1,add_b,add_b1;
	void del(){
		add_a=add_b=add_a1=add_b1=0;
	}
}s[N];
void pushup(int p){
	s[p].maxa=max(s[lc].maxa,s[rc].maxa);
	s[p].maxb=max(s[lc].maxb,s[rc].maxb);
	s[p].sum=s[lc].sum+s[rc].sum;
	if(s[lc].maxa>s[rc].maxa){
		s[p].se=max(s[lc].se,s[rc].maxa);
		s[p].cnt=s[lc].cnt;
	}
	if(s[lc].maxa<s[rc].maxa){
		s[p].se=max(s[rc].se,s[lc].maxa);
		s[p].cnt=s[rc].cnt;
	}
}
void build(int l,int r,int p){
	s[p].l=l,s[p].r=r;
	if(l==r){
		s[p].sum=s[p].maxa=s[p].maxb=read();
		s[p].se=-inf;
		s[p].cnt=1;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,lc);
	build(mid+1,r,rc);
	pushup(p);
}
void update(int k1,int k2,int k3,int k4,int p){
	s[p].sum=k1*s[p].cnt+k3*(s[p].r-s[p].l+1-s[p].cnt);
	s[p].maxb=max(s[p].maxb,s[p].maxa+k2);
	s[p].add_b=max(s[p].add_b,s[p].add_a+k2);
	s[p].add_b1=max(s[p].add_b1,s[p].add_a1+k4);
	s[p].maxa+=k1,s[p].add_a+=k1;
	s[p].add_a1+=k3;
	if(s[p].se>=-inf)s[p].se+=k3;
}
void pushdown(int p){
	if(s[lc].maxa>s[rc].maxa){
		update(s[p].add_a,s[p].add_b,s[p].add_a1,s[p].add_b1,lc);
		update(s[p].add_a1,s[p].add_b1,s[p].add_a1,s[p].add_b1,rc);
	}
	else if(s[lc].maxa<s[rc].maxa){
		update(s[p].add_a1,s[p].add_b1,s[p].add_a1,s[p].add_b1,lc);
		update(s[p].add_a,s[p].add_b,s[p].add_a1,s[p].add_b1,rc);
	}
	else{
		update(s[p].add_a,s[p].add_b,s[p].add_a1,s[p].add_b1,lc);
		update(s[p].add_a,s[p].add_b,s[p].add_a1,s[p].add_b1,rc);
	}
	s[p].del();
}
void add(int p,int l,int r,int k){
	if(s[p].l>r||s[p].r<l)return;
	if(l<=s[p].l&&r>=s[p].r){
		update(k,k,k,k,p);
		return;
	}
	pushdown(p);
	add(lc,l,r,k),add(rc,l,r,k);
	pushup(p);
}
void updatemin(int p,int l,int r,int v){
	if(s[p].l>r||s[p].r<l||v>=s[p].maxa)return;
	if(l<=s[p].l&&r>=s[p].r&&v>s[p].se){
		update(v-s[p].maxa,v-s[p].maxa,0,0,p);
		return;
	}
	pushdown(p);
	updatemin(lc,l,r,v),updatemin(rc,l,r,v);
	pushup(p);
}
int querysum(int p,int l,int r){
	if(s[p].l>r||l<s[p].r)return 0;
	if(l<=s[p].l&&r>=s[p].r)return s[p].sum;
	pushdown(p);
	return querysum(lc,l,r)+querysum(rc,l,r);
}
int querymaxa(int p,int l,int r){
	if(s[p].l>r||l<s[p].r)return -inf;
	if(l<=s[p].l&&r>=s[p].r)return s[p].maxa;
	pushdown(p);
	return max(querymaxa(lc,l,r),querymaxa(rc,l,r));
}
int querymaxb(int p,int l,int r){
	if(s[p].l>r||l<s[p].r)return -inf;
	if(l<=s[p].l&&r>=s[p].r)return s[p].maxb;
	pushdown(p);
	return max(querymaxb(lc,l,r),querymaxb(rc,l,r));
}
signed main(){
	scanf("%lld%lld",&n,&mm);
	build(1,n,1);
	for(int i=1;i<=mm;i++){
		int op=read(),l=read(),r=read(),k,v;
		//debug;
		if(op==1){
			k=read();
			add(1,l,r,k);
		}
		if(op==2){
			v=read();
			updatemin(1,l,r,v);
		}
		if(op==3)printf("%lld\n",querysum(1,l,r));
		if(op==4)printf("%lld\n",querymaxa(1,l,r));
		if(op==5)printf("%lld\n",querymaxb(1,l,r));
	}
	return 0;
}