#include<bits/stdc++.h>
#define ll long long
#define inf -2147483647
using namespace std;
const int N=500010;
int lbound[N<<2],rbound[N<<2];
int addmx1[N<<2],addmx2[N<<2];
int addse1[N<<2],addse2[N<<2];
int mx1[N<<2],mx2[N<<2],se[N<<2];
int cnt[N<<2],q[N]; ll sum[N<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p){
	sum[p]=sum[ls(p)]+sum[rs(p)];
	mx1[p]=max(mx1[ls(p)],mx1[rs(p)]);
	mx2[p]=max(mx2[ls(p)],mx2[rs(p)]);
	if(mx1[ls(p)]==mx1[rs(p)]){
		se[p]=max(se[ls(p)],se[rs(p)]);
		cnt[p]=cnt[ls(p)]+cnt[rs(p)];
	} else if(mx1[ls(p)]>mx1[rs(p)]){
		se[p]=max(se[ls(p)],mx1[rs(p)]);
		cnt[p]=cnt[ls(p)];
	} else{
		se[p]=max(mx1[ls(p)],se[rs(p)]);
		cnt[p]=cnt[rs(p)];
	}
}
void replace(int p,int d1,int d2,int b1,int b2){
	int pl=lbound[p]; int pr=rbound[p];
	sum[p]+=1LL*d1*cnt[p]+1LL*b1*(pr-pl+1-cnt[p]);
	mx2[p]=max(mx2[p],mx1[p]+d2);
	addmx2[p]=max(addmx2[p],addmx1[p]+d2);
	mx1[p]+=d1; addmx1[p]+=d1;
	addse2[p]=max(addse2[p],addse1[p]+b2);
	if(se[p]!=inf) se[p]+=b1; addse1[p]+=b1;
}
void pushdown(int p){ 
	int d1=addmx1[p],d2=addmx2[p];
	int b1=addse1[p],b2=addse2[p];
	if(mx1[ls(p)]>=mx1[rs(p)]) replace(ls(p),d1,d2,b1,b2);
	else replace(ls(p),b1,b2,b1,b2);
	if(mx1[rs(p)]>=mx1[ls(p)]) replace(rs(p),d1,d2,b1,b2);
	else replace(rs(p),b1,b2,b1,b2);
	addmx1[p]=addmx2[p]=addse1[p]=addse2[p]=0;
}
void build(int p,int pl,int pr){
	lbound[p]=pl; rbound[p]=pr;
	if(pl==pr){ se[p]=inf; cnt[p]=1;
		sum[p]=mx1[p]=mx2[p]=q[pl]; return;
	} int mid=pl+pr>>1; build(ls(p),pl,mid); 
	build(rs(p),mid+1,pr); pushup(p); return; 
}
void update1(int p,int pl,int pr,int l,int r,int d){
	if(l<=pl&&pr<=r){replace(p,d,d,d,d); return;}
	int mid=pl+pr>>1; pushdown(p);
	if(l<=mid) update1(ls(p),pl,mid,l,r,d);
	if(r>mid) update1(rs(p),mid+1,pr,l,r,d);
	pushup(p); return;
}
void update2(int p,int pl,int pr,int l,int r,int d){
	if(d>=mx1[p]) return; int q=d-mx1[p];
	if(l<=pl&&pr<=r&&se[p]<d){replace(p,q,q,0,0); return;} 
	int mid=pl+pr>>1; pushdown(p);
	if(l<=mid) update2(ls(p),pl,mid,l,r,d);
	if(r>mid) update2(rs(p),mid+1,pr,l,r,d);
	pushup(p); return;
}
ll querysum(int p,int pl,int pr,int l,int r){
	if(l<=pl&&pr<=r) return sum[p];
	int mid=pl+pr>>1; pushdown(p); ll res=0;
	if(l<=mid) res+=querysum(ls(p),pl,mid,l,r);
	if(r>mid) res+=querysum(rs(p),mid+1,pr,l,r);
	return res; 
}
int querymax1(int p,int pl,int pr,int l,int r){
	if(l<=pl&&pr<=r) return mx1[p];
	int mid=pl+pr>>1; pushdown(p); int res=inf;
	if(l<=mid) res=max(res,querymax1(ls(p),pl,mid,l,r));
	if(r>mid) res=max(res,querymax1(rs(p),mid+1,pr,l,r));
	return res; 	
}
int querymax2(int p,int pl,int pr,int l,int r){
	if(l<=pl&&pr<=r) return mx2[p];
	int mid=pl+pr>>1; pushdown(p); int res=inf;
	if(l<=mid) res=max(res,querymax2(ls(p),pl,mid,l,r));
	if(r>mid) res=max(res,querymax2(rs(p),mid+1,pr,l,r));
	return res; 	
}
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&q[i]);
	build(1,1,n); while(m--){
		int op,l,r,d;scanf("%d%d%d",&op,&l,&r);
		if(op==1) scanf("%d",&d),update1(1,1,n,l,r,d);
		else if(op==2) scanf("%d",&d),update2(1,1,n,l,r,d);
		else if(op==3) printf("%lld\n",querysum(1,1,n,l,r));
		else if(op==4) printf("%d\n",querymax1(1,1,n,l,r));
		else printf("%d\n",querymax2(1,1,n,l,r));
	}
	return 0;
}