rt.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls (rt<<1LL)
#define rs ((rt<<1LL)|1LL)
#define chmin(a,b) (a=min(a,b))
#define chmax(a,b) (a=max(a,b))
const int inf=0x3f3f3f3f3f3f3f3f;
struct tnode
{
	int sum,l,r,mx1,mx2,cnt,dmx,tag1,tag2,dtag1,dtag2;
	tnode(){}
	tnode(int _sum,int _l,int _r,int _mx1,int _mx2,int _cnt,int _dmx,int _tag1,int _tag2,int _dtag1,int _dtag2)
	{
		sum=_sum,l=_l,r=_r,mx1=_mx1,mx2=_mx2,cnt=_cnt,dmx=_dmx,tag1=_tag1,tag2=_tag2,dtag1=_dtag1,dtag2=_dtag2;
	}
}t[4000010];
void pushup(int rt)
{
	t[rt].sum=t[ls].sum+t[rs].sum;
	t[rt].mx1=max(t[ls].mx1,t[rs].mx1);
	t[rt].mx2=max(t[ls].mx2,t[rs].mx2);
	if(t[ls].mx1<t[rs].mx1)
	{
		t[rt].dmx=max(t[ls].mx1,t[rs].dmx);
		t[rt].cnt=t[rs].cnt;
	}
	else if(t[ls].mx1>t[rs].mx1)
	{
		t[rt].dmx=max(t[rs].mx1,t[ls].dmx);
		t[rt].cnt=t[ls].cnt;
	}
	else
	{
		t[rt].dmx=max(t[ls].dmx,t[rs].dmx);
		t[rt].cnt=t[ls].cnt+t[rs].cnt;
	}
}
void pushtag(int rt,int tag1,int tag2,int dtag1,int dtag2)
{
	t[rt].sum+=tag1*t[rt].cnt+dtag1*(t[rt].r-t[rt].l+1-t[rt].cnt);
	chmax(t[rt].mx2,t[rt].mx1+tag2);
	t[rt].mx1+=tag1;
	if(t[rt].dmx!=-inf)t[rt].dmx+=dtag1; 
	chmax(t[rt].tag2,t[rt].tag1+tag2);
	t[rt].tag1+=tag1;
	chmax(t[rt].dtag2,t[rt].dtag1+dtag2);
	t[rt].dtag1+=dtag1;
}
void pushdown(int rt)
{
	if(t[ls].mx1>=t[rs].mx1)pushtag(ls,t[rt].tag1,t[rt].tag2,t[rt].dtag1,t[rt].dtag2);
	else pushtag(ls,t[rt].dtag1,t[rt].dtag2,t[rt].dtag1,t[rt].dtag2);
	if(t[rs].mx1>=t[ls].mx1)pushtag(rs,t[rt].tag1,t[rt].tag2,t[rt].dtag1,t[rt].dtag2);
	else pushtag(rs,t[rt].dtag1,t[rt].dtag2,t[rt].dtag1,t[rt].dtag2);
	t[rt].tag1=t[rt].tag2=t[rt].dtag1=t[rt].dtag2=0;
}
void build(int rt,int l,int r,int *a)
{
	t[rt]=tnode(0,l,r,0,0,0,-inf,0,0,0,0);
	if(l==r)
	{
		t[rt].sum=t[rt].mx1=t[rt].mx2=a[l];
		t[rt].cnt=1;
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid,a);
	build(rs,mid+1,r,a);
	pushup(rt);
	return;
}
void add(int rt,int l,int r,int v)
{
	if(l==t[rt].l&&r==t[rt].r)
	{
		t[rt].sum+=v*(t[rt].r-t[rt].l+1);
		t[rt].mx1+=v;
		chmax(t[rt].mx2,t[rt].mx1);
		if(t[rt].dmx!=-inf)t[rt].dmx+=v;
		t[rt].tag1+=v;
		chmax(t[rt].tag2,t[rt].tag1); 
		t[rt].dtag1+=v;
		chmax(t[rt].dtag2,t[rt].dtag1); 
		return;
	}
	pushdown(rt);
	if(l<=t[ls].r)add(ls,l,min(r,t[ls].r),v);
	if(r>=t[rs].l)add(rs,max(l,t[rs].l),r,v);
	pushup(rt);
	return;
}
void cmin(int rt,int l,int r,int v)
{
	if(v>=t[rt].mx1)return;
	if(l==t[rt].l&&r==t[rt].r&&v>t[rt].dmx)
	{
		t[rt].sum-=(t[rt].mx1-v)*t[rt].cnt;
		t[rt].tag1-=t[rt].mx1-v;
		t[rt].mx1=v;
		return;
	}
	pushdown(rt);
	if(l<=t[ls].r&&t[ls].mx1>v)cmin(ls,l,min(r,t[ls].r),v);
	if(r>=t[rs].l&&t[rs].mx1>v)cmin(rs,max(l,t[rs].l),r,v);
	pushup(rt);
	return;
}
int qsum(int rt,int l,int r)
{
	if(l==t[rt].l&&r==t[rt].r)return t[rt].sum;
	pushdown(rt);
	int ans=0;
	if(l<=t[ls].r)ans+=qsum(ls,l,min(r,t[ls].r));
	if(r>=t[rs].l)ans+=qsum(rs,max(l,t[rs].l),r);
	pushup(rt);
	return ans;
}
int qmx1(int rt,int l,int r)
{
	if(l==t[rt].l&&r==t[rt].r)return t[rt].mx1;
	pushdown(rt);
	int ans=-inf;
	if(l<=t[ls].r)chmax(ans,qmx1(ls,l,min(r,t[ls].r)));
	if(r>=t[rs].l)chmax(ans,qmx1(rs,max(l,t[rs].l),r));
	pushup(rt);
	return ans;
}
int qmx2(int rt,int l,int r)
{
	if(l==t[rt].l&&r==t[rt].r)return t[rt].mx2;
	pushdown(rt);
	int ans=-inf;
	if(l<=t[ls].r)chmax(ans,qmx2(ls,l,min(r,t[ls].r)));
	if(r>=t[rs].l)chmax(ans,qmx2(rs,max(l,t[rs].l),r));
	pushup(rt);
	return ans;
}
int n,q,a[500010];
void output()
{
	for(int i=1;i<=(n<<2);i++)
	{
		cout<<"id="<<i<<":";
		cout<<"l="<<t[i].l<<",r="<<t[i].r<<",sum="<<t[i].sum<<",mx1="<<t[i].mx1<<",cnt="<<t[i].cnt<<",dmx="<<t[i].dmx<<",mx2="<<t[i].mx2<<",tag1="<<t[i].tag1<<",tag2="<<t[i].tag2<<",dtag1="<<t[i].dtag1<<",dtag2="<<t[i].dtag2<<endl;
	}
	cout<<endl;
}
signed main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n,a);
	while(q--)
	{
//		output();
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r,v;
			cin>>l>>r>>v;
			add(1,l,r,v);
		}
		else if(op==2)
		{
			int l,r,v;
			cin>>l>>r>>v;
			cmin(1,l,r,v);
		}
		else if(op==3)
		{
			int l,r;
			cin>>l>>r;
			cout<<qsum(1,l,r)<<endl;
		}
		else if(op==4)
		{
			int l,r;
			cin>>l>>r;
			cout<<qmx1(1,l,r)<<endl;
		}
		else
		{
			int l,r;
			cin>>l>>r;
			cout<<qmx2(1,l,r)<<endl;
		}
	}
	return 0;
}