/*
Author:qhzx_FeS2_Butterfly
Start Coding:2024.3.11 11:21
Finish Debugging:
Algorithm:Ji Segment Tree/Segment Tree Beat
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005,INF=0x3f3f3f3f;
int a[N];
struct SegmentTreeBeat
{
	struct node
	{
		int l,r,mxn,mxh,smx,mxc,sum,lz1n,lz1h,lz2n,lz2h;
		#define l(u) sg[u].l
		#define r(u) sg[u].r
		#define len(u) (r(u)-l(u)+1)
		#define mxn(u) sg[u].mxn
		#define mxh(u) sg[u].mxh
		#define smx(u) sg[u].smx
		#define mxc(u) sg[u].mxc
		#define sum(u) sg[u].sum
		#define lz1n(u) sg[u].lz1n
		#define lz1h(u) sg[u].lz1h
		#define lz2n(u) sg[u].lz2n
		#define lz2h(u) sg[u].lz2h
	}sg[N<<2];
	#define lc (u<<1)
	#define rc (u<<1|1)
	void pushup(int u)
	{
		sum(u)=sum(lc)+sum(rc);
		mxh(u)=max(mxh(lc),mxh(rc));
		if(mxn(lc)==mxn(rc))
		{
			mxn(u)=mxn(lc);
			smx(u)=max(smx(lc),smx(rc));
			mxc(u)=mxc(lc)+mxc(rc);
		}
		else if(mxn(lc)>mxn(rc))
		{
			mxn(u)=mxn(lc);
			smx(u)=max(smx(lc),mxn(rc));
			mxc(u)=mxc(lc);
		}
		else
		{
			mxn(u)=mxn(rc);
			smx(u)=max(mxn(lc),smx(rc));
			mxc(u)=mxc(rc);
		}
	}
	void pushlazy(int u,int l1,int L1,int l2,int L2)
	{
		sum(u)+=l1*mxc(u)+l2*(len(u)-mxc(u));
		mxh(u)=max(mxh(u),mxh(u)+L1);
		lz1h(u)=max(lz1h(u),lz1h(u)+L1);
		mxn(u)+=l1;
		lz1n(u)+=l1;
		lz2h(u)=max(lz2h(u),lz2h(u)+L2);
		if(smx(u)!=-INF)smx(u)+=l2;
		lz2n(u)+=l2;
	}
	void pushdown(int u)
	{
		if(mxn(lc)>mxn(rc))
		{
			pushlazy(lc,lz1n(u),lz1h(u),lz2n(u),lz2h(u));
			pushlazy(rc,lz2n(u),lz2h(u),lz2n(u),lz2h(u));
		}
		else if(mxn(rc)>mxn(lc))
		{
			pushlazy(rc,lz1n(u),lz1h(u),lz2n(u),lz2h(u));
			pushlazy(lc,lz2n(u),lz2h(u),lz2n(u),lz2h(u));
		}
		else
		{
			pushlazy(lc,lz1n(u),lz1h(u),lz2n(u),lz2h(u));
			pushlazy(rc,lz1n(u),lz1h(u),lz2n(u),lz2h(u));
		}
		lz1n(u)=lz1h(u)=lz2n(u)=lz2h(u)=0;
	}
	void build(int u,int l,int r)
	{
		l(u)=l;r(u)=r;
		lz1n(u)=lz1h(u)=lz2n(u)=lz2h(u)=0;
		if(l==r)
		{
			sum(u)=mxn(u)=mxh(u)=a[l];
			smx(u)=-INF;mxc(u)=1;
			return;
		}
		int mid=l+r>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		pushup(u);
	}
	void updates(int u,int l,int r,int v)
	{
		if(l(u)>r||r(u)<l)return;
		if(l<=l(u)&&r(u)<=r)
		{
			pushlazy(u,v,v,v,v);
			return;
		}
		pushdown(u);
		updates(lc,l,r,v);
		updates(rc,l,r,v);
		pushup(u);
	}
	void updatem(int u,int l,int r,int v)
	{
		if(l(u)>r||r(u)<l||v>=mxn(u))return;
		if(l<=l(u)&&r(u)<=r&&v>smx(u))
		{
			pushlazy(u,v-mxn(u),v-mxn(u),0,0);
			return;
		}
		pushdown(u);
		updatem(lc,l,r,v);
		updatem(rc,l,r,v);
		pushup(u);
	}
	int querys(int u,int l,int r)
	{
		if(l(u)>r||r(u)<l)return 0;
		if(l<=l(u)&&r(u)<=r)return sum(u);
		pushdown(u);
		return querys(lc,l,r)+querys(rc,l,r);
	}
	int querym(int u,int l,int r)
	{
		if(l(u)>r||r(u)<l)return -INF;
		if(l<=l(u)&&r(u)<=r)return mxn(u);
		pushdown(u);
		return max(querym(lc,l,r),querym(rc,l,r));
	}
	int queryhm(int u,int l,int r)
	{
		if(l(u)>r||r(u)<l)return -INF;
		if(l<=l(u)&&r(u)<=r)return mxh(u);
		pushdown(u);
		return max(queryhm(lc,l,r),queryhm(rc,l,r));
	}
}sgb;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sgb.build(1,1,n);
	for(int i=1,op,l,r,v;i<=m;i++)
	{
		cin>>op>>l>>r;
		if(op==1)
		{
			cin>>v;
			sgb.updates(1,l,r,v);
		}
		if(op==2)
		{
			cin>>v;
			sgb.updatem(1,l,r,v);
		}
		if(op==3)cout<<sgb.querys(1,l,r)<<'\n';
		if(op==4)cout<<sgb.querym(1,l,r)<<'\n';
		if(op==5)cout<<sgb.queryhm(1,l,r)<<'\n';
	}
}