#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long LL;
typedef unsigned int UI;
typedef unsigned long long ULL;
int n,m,a[N];
struct SegmentTree
{
	int l,r,mxa,mxb,cnt,se,add1,add2,add3,add4;
	LL sum;
	#define l(p) tr[p].l
	#define r(p) tr[p].r
	#define mxa(p) tr[p].mxa
	#define mxb(p) tr[p].mxb
	#define cnt(p) tr[p].cnt
	#define se(p) tr[p].se
	#define add1(p) tr[p].add1
	#define add2(p) tr[p].add2
	#define add3(p) tr[p].add3
	#define add4(p) tr[p].add4
	#define sum(p) tr[p].sum
}tr[N<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void pushup(int p)
{
	sum(p)=sum(ls(p))+sum(rs(p));
	mxa(p)=max(mxa(ls(p)),mxa(rs(p)));
	mxb(p)=max(mxb(ls(p)),mxb(rs(p)));
	if(mxa(ls(p))==mxa(rs(p)))
	{
		se(p)=max(se(ls(p)),se(rs(p)));
		cnt(p)=cnt(ls(p))+cnt(rs(p));
	}
	else if(mxa(ls(p))>mxa(rs(p)))
	{
		se(p)=max(se(ls(p)),se(rs(p)));
		cnt(p)=cnt(ls(p));
	}
	else
	{
		se(p)=max(mxa(ls(p)),se(rs(p)));
		cnt(p)=cnt(p)=cnt(rs(p));
	}
}
inline void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r)
	{
		sum(p)=mxa(p)=mxb(p)=a[l];
		cnt(p)=1,se(p)=INT_MIN;
		return;
	}
	int mid=l+((r-l)>>1);
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
inline void update(int p,int k1,int k2,int k3,int k4)
{
	sum(p)+=1LL*k1*cnt(p)+1LL*k2*(r(p)-l(p)+1-cnt(p));
	mxb(p)=max(mxb(p),mxa(p)+k3);
	mxa(p)+=k1;
	if(se(p)!=INT_MIN) se(p)+=k2;
	add3(p)=max(add3(p),add1(p)+k3);
	add4(p)=max(add4(p),add2(p)+k4);
	add1(p)+=k1,add2(p)+=k2;
}
inline void spread(int p)
{
	int maxn=max(mxa(ls(p)),mxa(rs(p)));
	if(mxa(ls(p))==maxn) update(ls(p),add1(p),add2(p),add3(p),add4(p));
	else update(ls(p),add2(p),add2(p),add4(p),add4(p));
	if(mxa(rs(p))==maxn) update(rs(p),add1(p),add2(p),add3(p),add4(p));
	else update(rs(p),add2(p),add2(p),add4(p),add4(p));
	add1(p)=add2(p)=add3(p)=add4(p)=0;
}
inline void Add(int p,int l,int r,int k)
{
	if(l<=l(p)&&r(p)<=r)
	{
		sum(p)+=1LL*k*cnt(p)+1LL*k*(r(p)-l(p)+1-cnt(p));
		mxa(p)+=k;
		mxb(p)=max(mxb(p),mxa(p));
		if(se(p)!=INT_MIN) se(p)+=k;
		add1(p)+=k,add2(p)+=k;
		add3(p)=max(add3(p),add1(p));
		add4(p)=max(add4(p),add2(p));
		return;
	}
	spread(p);
	int mid=l(p)+((r(p)-l(p))>>1);
	if(l<=mid) Add(ls(p),l,r,k);
	if(mid<r) Add(rs(p),l,r,k);
	pushup(p);
}
inline void change(int p,int l,int r,int k)
{
	if(l>r(p)||r<l(p)||k>=mxa(p)) return;
	else if(l<=l(p)&&r(p)<=r&&se(p)<k)
	{
		int tmp=mxa(p)-k;
		sum(p)-=1LL*tmp*cnt(p);
		mxa(p)=k,add1(p)-=tmp;
		return;
	}
	spread(p);
	change(ls(p),l,r,k);
	change(rs(p),l,r,k);
	pushup(p);
}
inline LL query(int p,int l,int r)
{
	if(l<=l(p)&&r(p)<=r) return sum(p);
	spread(p);
	int mid=l(p)+((r(p)-l(p))>>1);
	LL ans=0;
	if(l<=mid) ans+=query(ls(p),l,r);
	if(mid<r) ans+=query(rs(p),l,r);
	return ans;
}
inline int getmaxa(int p,int l,int r)
{
	if(l<=l(p)&&r(p)<=r) return mxa(p);
	spread(p);
	int mid=l(p)+((r(p)-l(p))>>1),mx=INT_MIN;
	if(l<=mid) mx=max(mx,getmaxa(ls(p),l,r));
	if(mid<r) mx=max(mx,getmaxa(rs(p),l,r));
	return mx;
}
inline int getmaxb(int p,int l,int r)
{
	if(l<=l(p)&&r(p)<=r) return mxb(p);
	spread(p);
	int mid=l(p)+((r(p)-l(p))>>1),mx=INT_MIN;
	if(l<=mid) mx=max(mx,getmaxb(ls(p),l,r));
	if(mid<r) mx=max(mx,getmaxb(rs(p),l,r));
	return mx;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--)
	{
		int type,l,r;
		cin>>type>>l>>r;
		if(type==1)
		{
			int k;cin>>k;
			Add(1,l,r,k);
		}
		else if(type==2)
		{
			int k;cin>>k;
			change(1,l,r,k);
		}
		else if(type==3) cout<<query(1,l,r)<<'\n';
		else if(type==4) cout<<getmaxa(1,l,r)<<'\n';
		else cout<<getmaxb(1,l,r)<<'\n';
	}
	return 0;
}