#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	char ch=getchar();
	bool f=false;
	int num=0;
	while(!isdigit(ch))f=(ch=='-'?true:0),ch=getchar();
	while(isdigit(ch))num=(num<<1)+(num<<3)+(ch&15),ch=getchar();
	return f?-num:num;
}
inline int mmax(int a,int b){return a<b?b:a;}
#define maxn 2000200
#define inf -2e9+7
#define mid (L+R>>1)
int t[maxn],mx[maxn],mn[maxn],laz1[maxn],laz2[maxn],laz3[maxn],laz4[maxn],b[maxn],ls[maxn],rs[maxn],l[maxn],r[maxn],cnt[maxn],fa[maxn];
inline void push_up(int id){
	t[id]=t[ls[id]]+t[rs[id]];
	if(mx[ls[id]]==mx[rs[id]])mx[id]=mx[ls[id]],cnt[id]=cnt[ls[id]]+cnt[rs[id]],mn[id]=mmax(mn[ls[id]],mn[rs[id]]);
	else if(mx[ls[id]]>mx[rs[id]])mx[id]=mx[ls[id]],cnt[id]=cnt[ls[id]],mn[id]=mmax(mn[ls[id]],mx[rs[id]]);
	else mx[id]=mx[rs[id]],cnt[id]=cnt[rs[id]],mn[id]=mmax(mn[rs[id]],mx[ls[id]]);
	b[id]=mmax(b[id],mx[id]);
}
inline void build(int L,int R,int id){
	r[id]=R,l[id]=L;
	if(L==R){
		mn[id]=inf;
		t[id]=read();
		mx[id]=t[id];
		cnt[id]=1;
		b[id]=t[id];
		return;
	}
	ls[id]=id<<1,rs[id]=ls[id]|1;
	fa[ls[id]]=fa[rs[id]]=id;
	build(L,mid,ls[id]);
	build(mid+1,R,rs[id]);
	push_up(id);
}
inline void updatemx(int id){
	t[id]+=laz1[fa[id]]*cnt[id]+(r[id]-l[id]+1-cnt[id])*laz2[fa[id]];
	b[id]=mmax(b[id],mx[id]+laz3[fa[id]]);
	mx[id]+=laz1[fa[id]];
	laz4[id]=mmax(laz4[id],laz4[fa[id]]+laz2[id]);
	laz3[id]=mmax(laz3[id],laz3[fa[id]]+laz1[id]);
	if(mn[id]!=inf){
		mn[id]+=laz2[fa[id]];
	}
	laz1[id]+=laz1[fa[id]],laz2[id]+=laz2[fa[id]];
}
inline void updatemn(int id){
	t[id]+=laz2[fa[id]]*(r[id]-l[id]+1);
	b[id]=mmax(b[id],mx[id]+laz4[fa[id]]);
	mx[id]+=laz2[fa[id]];
	laz3[id]=mmax(laz3[id],laz4[fa[id]]+laz1[id]);
	laz4[id]=mmax(laz4[id],laz4[fa[id]]+laz2[id]);
	if(mn[id]!=inf){
		mn[id]+=laz2[fa[id]];
	}
	laz1[id]+=laz2[fa[id]],laz2[id]+=laz2[fa[id]];
}
inline void push_down(int id){
	long long mxx=mmax(mx[ls[id]],mx[rs[id]]);
	if(mxx==mx[ls[id]]) updatemx(ls[id]);
	else updatemn(ls[id]);
	if(mxx==mx[rs[id]]) updatemx(rs[id]);
	else updatemn(rs[id]);
	laz1[id]=laz2[id]=laz3[id]=laz4[id]=0;
}
inline void add(int id,int val,int R,int L){
	if(L>r[id]||R<l[id])return;
	if(L<=l[id]&&r[id]<=R){
		t[id]+=(r[id]-l[id]+1)*val;
		laz1[id]+=val,laz2[id]+=val;
		laz3[id]=mmax(laz3[id],laz1[id]),laz4[id]=mmax(laz2[id],laz4[id]);
		mx[id]+=val;
		b[id]=mmax(b[id],mx[id]);
		if(mn[id]!=inf)mn[id]+=val;
		return;
	}
	push_down(id);
	add(ls[id],val,R,L);
	add(rs[id],val,R,L);
	push_up(id);
}
inline void moditfy(int id,int val,int R,int L){
	if(L>r[id]||R<l[id]||mx[id]<=val)return;
	if(L<=l[id]&&r[id]<=R&&mn[id]<val){
		t[id]-=(mx[id]-val)*cnt[id];
		laz1[id]-=mx[id]-val;
		mx[id]=val;
		return;
	}
	push_down(id);
	moditfy(ls[id],val,R,L);
	moditfy(rs[id],val,R,L);
	push_up(id);
}
inline long long query_sum(int id,int R,int L){
	if(L>r[id]||R<l[id])return 0;
	if(L<=l[id]&&r[id]<=R)return t[id];
	push_down(id);
	return query_sum(ls[id],R,L)+query_sum(rs[id],R,L);
}
inline long long querymaxa(int id,int R,int L){
	if(L>r[id]||R<l[id])return inf;
	if(L<=l[id]&&r[id]<=R)return mx[id];
	push_down(id);
	return mmax(querymaxa(ls[id],R,L),querymaxa(rs[id],R,L));
}
inline long long querymaxb(int id,int R,int L){
	if(L>r[id]||R<l[id])return inf;
	if(L<=l[id]&&r[id]<=R)return b[id];
	push_down(id);
	return mmax(querymaxb(ls[id],R,L),querymaxb(rs[id],R,L));
}
// inline void Print(int id){
	// printf("(%d,%d):区间和(%d);最大值(%d),次大值(%d);历史最大值(%d),最大值个数(%d)\n",l[id],r[id],t[id],mx[id],mn[id],b[id],cnt[id]);
	// if(l[id]==r[id])return;
	// push_down(id);
	// Print(ls[id]);
	// Print(rs[id]);
// }
signed main(){
	int n=read(),m=read()+1;
	build(1,n,1);
	int kkksc,kkks=0;
	// Print(1);
	while(--m){
		int op=read(),l=read(),r=read();
		// printf("%lld\n",op);
		// cout<<m<<'\n';
		switch(op){
			case 1:
				add(1,read(),r,l);
				break;
			case 2:
				moditfy(1,read(),r,l);
				break;
			case 3:
				printf("%lld\n",query_sum(1,r,l));
				break;
			case 4:
				printf("%lld\n",querymaxa(1,r,l));
				break;
			case 5:
				printf("%lld\n",querymaxb(1,r,l));
				break;
		}
	}
	return 0;
}