//segment tree beats
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls rt<<1
#define rs rt<<1|1
#define mid l+r>>1
#define len r-l+1
#define llen mid-l+1
#define rlen r-mid

const int MAXN=5e5+10;
const int INF=LONG_LONG_MAX;

int n,m,num[MAXN];
struct Node
{
	int tot;
	int maxst,maxnd,maxnum,lzyst,lzynd;//A array -present
	int maxhis,lzysth,lzyndh;//B array -history
}sum[MAXN<<2];

void maintain(int rt)
{
	sum[rt].tot=sum[ls].tot+sum[rs].tot;
	
	sum[rt].maxst=max(sum[ls].maxst,sum[rs].maxst);
	if(sum[ls].maxst==sum[rs].maxst)
	{
		sum[rt].maxnum=sum[ls].maxnum+sum[rs].maxnum;
		sum[rt].maxnd=max(sum[ls].maxnd,sum[rs].maxnd);
	}
	else 
	{
		sum[rt].maxnum=sum[ls].maxst>sum[rs].maxst?sum[ls].maxnum:sum[rs].maxnum;
		sum[rt].maxnd=sum[ls].maxst>sum[rs].maxst?max(sum[rs].maxst,sum[ls].maxnd):max(sum[ls].maxst,sum[rs].maxnd);
	}
	
	sum[rt].maxhis=max(sum[ls].maxhis,sum[rs].maxhis);
	
	return ;
}

void build(int rt,int l,int r)
{
	if(l==r)
	{
		sum[rt].tot=sum[rt].maxst=sum[rt].maxhis=num[l];
		sum[rt].maxnum=1;
		sum[rt].maxnd=-INF;
		return ;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	maintain(rt);
	return ;
}

void pushdown(int rt,int l,int r)
{
	int max_cld=max(sum[ls].maxst,sum[rs].maxst);
	
	if(sum[ls].maxst==max_cld)
	{
		sum[ls].tot+=(sum[ls].maxnum*sum[rt].lzyst+(llen-sum[ls].maxnum)*sum[rt].lzynd);
		
		sum[ls].maxhis=max(sum[ls].maxhis,sum[ls].maxst+sum[rt].lzysth);
		sum[ls].lzysth=max(sum[ls].lzysth,sum[ls].lzyst+sum[rt].lzysth);
		sum[ls].lzyndh=max(sum[ls].lzyndh,sum[ls].lzynd+sum[rt].lzyndh);
		
		sum[ls].maxst+=sum[rt].lzyst;
		sum[ls].lzyst+=sum[rt].lzyst;
		if(sum[ls].maxnd!=-INF)sum[ls].maxnd+=sum[rt].lzynd;
		sum[ls].lzynd+=sum[rt].lzynd;
	}
	else
	{
		sum[ls].tot+=(sum[ls].maxnum*sum[rt].lzynd+(llen-sum[ls].maxnum)*sum[rt].lzynd);
		
		sum[ls].maxhis=max(sum[ls].maxhis,sum[ls].maxst+sum[rt].lzyndh);
		sum[ls].lzysth=max(sum[ls].lzysth,sum[ls].lzyst+sum[rt].lzyndh);
		sum[ls].lzyndh=max(sum[ls].lzyndh,sum[ls].lzynd+sum[rt].lzyndh);
		
		sum[ls].maxst+=sum[rt].lzynd;
		sum[ls].lzyst+=sum[rt].lzynd;
		if(sum[ls].maxnd!=-INF)sum[ls].maxnd+=sum[rt].lzynd;
		sum[ls].lzynd+=sum[rt].lzynd;
	}
	
	if(sum[rs].maxst==max_cld)
	{
		sum[rs].tot+=(sum[rs].maxnum*sum[rt].lzyst+(rlen-sum[rs].maxnum)*sum[rt].lzynd);
		
		sum[rs].maxhis=max(sum[rs].maxhis,sum[rs].maxst+sum[rt].lzysth);
		sum[rs].lzysth=max(sum[rs].lzysth,sum[rs].lzyst+sum[rt].lzysth);
		sum[rs].lzyndh=max(sum[rs].lzyndh,sum[rs].lzynd+sum[rt].lzyndh);
		
		sum[rs].maxst+=sum[rt].lzyst;
		sum[rs].lzyst+=sum[rt].lzyst;
		if(sum[rs].maxnd!=-INF)sum[rs].maxnd+=sum[rt].lzynd;
		sum[rs].lzynd+=sum[rt].lzynd;
	}
	else
	{
		sum[rs].tot+=(sum[rs].maxnum*sum[rt].lzynd+(rlen-sum[rs].maxnum)*sum[rt].lzynd);
		
		sum[rs].maxhis=max(sum[rs].maxhis,sum[rs].maxst+sum[rt].lzyndh);
		sum[rs].lzysth=max(sum[rs].lzysth,sum[rs].lzyst+sum[rt].lzyndh);
		sum[rs].lzyndh=max(sum[rs].lzyndh,sum[rs].lzynd+sum[rt].lzyndh);
		
		sum[rs].maxst+=sum[rt].lzynd;
		sum[rs].lzyst+=sum[rt].lzynd;
		if(sum[rs].maxnd!=-INF)sum[rs].maxnd+=sum[rt].lzynd;
		sum[rs].lzynd+=sum[rt].lzynd;
	}
	
	sum[rt].lzyst=0;
	sum[rt].lzysth=0;
	sum[rt].lzynd=0;
	sum[rt].lzyndh=0;
	return ;
}

void add(int rt,int l,int r,int ql,int qr,int w)
{
	if(ql>r||qr<l)return;
	if(ql<=l&&r<=qr)
	{
		sum[rt].tot+=len*w;
		
		sum[rt].maxst+=w;
		sum[rt].lzyst+=w;
		if(sum[rt].maxnd!=-INF)sum[rt].maxnd+=w;
		sum[rt].lzynd+=w;
		
		sum[rt].maxhis=max(sum[rt].maxhis,sum[rt].maxst);
		sum[rt].lzysth=max(sum[rt].lzysth,sum[rt].lzyst);
		sum[rt].lzyndh=max(sum[rt].lzyndh,sum[rt].lzynd);
		
		return ;
	}
	pushdown(rt,l,r);
	add(ls,l,mid,ql,qr,w);
	add(rs,mid+1,r,ql,qr,w);
	maintain(rt);
	return ;
}

void cover(int rt,int l,int r,int ql,int qr,int w)
{
	if(ql>r||qr<l||sum[rt].maxst<=w)return;
	if(ql<=l&&r<=qr&&sum[rt].maxnd<w)
	{
		sum[rt].tot-=(sum[rt].maxnum*(sum[rt].maxst-w));
		
		sum[rt].maxst=w;
		sum[rt].lzyst+=(w-sum[rt].maxst);
		
		sum[rt].maxhis=max(sum[rt].maxhis,w);
		sum[rt].lzysth=max(sum[rt].lzysth,sum[rt].lzyst);
				
		return ;
	}
	pushdown(rt,l,r);
	cover(ls,l,mid,ql,qr,w);
	cover(rs,mid+1,r,ql,qr,w);
	maintain(rt);
	return ;
}

Node query(int rt,int l,int r,int ql,int qr)
{
	if(ql>r||qr<l)
	{
		Node k={0,-INF,-INF,0,0,0,-INF,0,0};
		return k;
	}
	if(ql<=l&&r<=qr)return sum[rt];
	pushdown(rt,l,r);
	Node left=query(ls,l,mid,ql,qr),right=query(rs,mid+1,r,ql,qr);
	return {left.tot+right.tot,max(left.maxst,right.maxst),max(left.maxnd,right.maxnd),0,0,0,max(left.maxhis,right.maxhis),0,0};
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>num[i];
	
	build(1,1,n);
	
	while(m--)
	{
		int oper,l,r;
		cin>>oper>>l>>r;
		
		if(oper==1)
		{
			int k;cin>>k;
			add(1,1,n,l,r,k);
		}
		else if(oper==2)
		{
			int v;cin>>v;
			cover(1,1,n,l,r,v);
		}
		else if(oper==3)
			cout<<query(1,1,n,l,r).tot<<'\n';
		else if(oper==4)
			cout<<query(1,1,n,l,r).maxst<<'\n';
		else //if(oper==5)
			cout<<query(1,1,n,l,r).maxhis<<'\n';
	}
	return 0;
}