#include<bits/stdc++.h>
#define int long long
#define ri register int
#define ls (id<<1)
#define mid (l+r>>1)
#define rs ((id<<1)|1)
const int minf=-1145141919810ll;
const int maxf=1145141919810ll;
using namespace std;
namespace JYAorz{
	char buf[1<<20],*p1,*p2;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	inline int r(){
		int J=1,Y=0;char A=getchar();while(A>'9'||A<'0'){if(A=='-')J=-1;A=getchar();}
		while(A<='9'&&A>='0'){Y=(Y<<1)+(Y<<3)+(A^48);A=getchar();}return J*Y;
	}
	inline void WI(int ORZ){if(ORZ==0)return;if(ORZ<0){ORZ=-ORZ;putchar('-');}WI(ORZ/10);putchar(48+ORZ%10);}
	inline void ww(int STO){if(STO!=0)WI(STO);else putchar('0');putchar(' ');}
	inline void wln(int STO){if(STO!=0)WI(STO);else putchar('0');putchar('\n');}
	inline void w(int STO){if(STO!=0)WI(STO);else putchar('0');}
}
using namespace JYAorz;
namespace YSCorz{
	int n,m,lf,rf,a[1919810],k;
	struct sgt{
		int lz1,lz2,lz3,lz4;
		int sum,ma1,ma2,l,r,s,t;
	}s[2010000];
	inline void up(int id){
		s[id].sum=s[ls].sum+s[rs].sum;
		s[id].ma1=max(s[ls].ma1,s[rs].ma1);
		s[id].ma2=max(s[ls].ma2,s[rs].ma2);
		if(s[ls].ma1==s[rs].ma1){
			s[id].s=max(s[ls].s,s[rs].s);
			s[id].t=s[ls].t+s[rs].t;
		}   
		else if(s[ls].ma1>s[rs].ma1){
			s[id].s=max(s[ls].s,s[rs].ma1);
			s[id].t=s[ls].t;
		}
		else{
			s[id].s=max(s[rs].s,s[ls].ma1);
			s[id].t=s[rs].t;
		}
	}
	inline void down(int id,int t1,int t2,int t3,int t4){
		s[id].sum+=t1*s[id].t+t2*(s[id].r-s[id].l-s[id].t+1);
		s[id].ma2=max(s[id].ma2,s[id].ma1+t3);
		s[id].ma1+=t1;
		if(s[id].s!=minf)s[id].s+=t2;
		s[id].lz3=max(s[id].lz3,s[id].lz1+t3);
		s[id].lz4=max(s[id].lz4,s[id].lz2+t4);
		s[id].lz1+=t1;s[id].lz2+=t2;
	}
	inline void dw(int id){
		int Max=max(s[ls].ma1,s[rs].ma1);
		if(s[ls].ma1==Max)down(ls,s[id].lz1,s[id].lz2,s[id].lz3,s[id].lz4);
		else down(ls,s[id].lz2,s[id].lz2,s[id].lz3,s[id].lz4);
		if(s[rs].ma1==Max)down(rs,s[id].lz1,s[id].lz2,s[id].lz3,s[id].lz4);
		else down(rs,s[id].lz2,s[id].lz2,s[id].lz3,s[id].lz4);
		s[id].lz1=s[id].lz2=s[id].lz3=s[id].lz4=0;
	}
	inline void bui(int l,int r,int id){
		s[id].l=l,s[id].r=r;
		s[id].lz1=s[id].lz2=s[id].lz3=s[id].lz4=0;
		if(l==r){
			s[id].sum=s[id].ma1=s[id].ma2=a[l];
			s[id].t=1;
			s[id].s=minf;
		}
		else{
			bui(l,mid,ls);
			bui(mid+1,r,rs);
			up(id);
		}
	}
	inline void add(int id){
		int l=s[id].l,r=s[id].r;
		if(lf<=l&&rf>=r){
			s[id].sum+=k*(s[id].r-s[id].l+1);
			s[id].ma1+=k;
			s[id].ma2=max(s[id].ma2,s[id].ma1);
			if(s[id].s!=minf)s[id].s+=k;
			s[id].lz1+=k;s[id].lz2+=k;
			s[id].lz3=max(s[id].lz3,s[id].lz1);
			s[id].lz4=max(s[id].lz4,s[id].lz2);
			return;
		}
		dw(id);
		if(lf<=mid)add(ls);
		if(mid<rf)add(rs);
		up(id);
	}
	inline void mi(int id){
		int l=s[id].l,r=s[id].r;
		if(s[id].ma1<=k)return;
		if(lf<=l&&rf>=r&&s[id].s<k){
			int x=s[id].ma1-k;
			s[id].sum-=s[id].t*x;
			s[id].ma1=k,s[id].lz1-=x;
			return;
		}
		dw(id);
		if(lf<=mid)mi(ls);
		if(mid<rf)mi(rs);
		up(id);
	}
	inline int qsum(int id){
		dw(id);
		int l=s[id].l,r=s[id].r;
		if(lf<=l&&rf>=r)return s[id].sum;
		int S=0;
		if(lf<=mid)S+=qsum(ls);
		if(mid<rf)S+=qsum(rs);
		return S;
	}
	inline int qmax1(int id){
		dw(id);
		int l=s[id].l,r=s[id].r;
		if(lf<=l&&rf>=r)return s[id].ma1;
		int S=minf;
		if(lf<=mid)S=max(S,qmax1(ls));
		if(mid<rf)S=max(S,qmax1(rs));
		return S;
	}
	inline int qmax2(int id){
		dw(id);
		int l=s[id].l,r=s[id].r;
		if(lf<=l&&rf>=r)return s[id].ma2;
		int S=minf;
		if(lf<=mid)S=max(S,qmax2(ls));
		if(mid<rf)S=max(S,qmax2(rs));
		return S;
	}
	inline void stoorz(){
		n=r(),m=r();
		for(ri i=1;i<=n;++i)a[i]=r();
		bui(1,n,1);
		while(m--){
			int op=r();
			lf=r(),rf=r();
			if(op==1)k=r(),add(1);
			if(op==2)k=r(),mi(1);
			if(op==3)wln(qsum(1));
			if(op==4)wln(qmax1(1));
			if(op==5)wln(qmax2(1));
		}
	}
}
signed main(){YSCorz::stoorz();}