#include<bits/stdc++.h>
using namespace std;
#define MAXN 500001
#define inf 1e18
#define int long long
#define R register
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+c-48;
		c=getchar();
	}
	return x*f;
}
int a[MAXN];
struct SegmentTree{
	struct node{
		int l,r;
		int add_a1,add_a2,add_b1,add_b2;
		int sum,maxa,maxb,second,cnt;
	} tree[MAXN<<2];
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
	inline void push_up(int p)
	{
		tree[p].maxa=max(tree[ls(p)].maxa,tree[rs(p)].maxa);
		tree[p].maxb=max(tree[ls(p)].maxb,tree[rs(p)].maxb);
		tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
		if(tree[ls(p)].maxa==tree[rs(p)].maxa)
		{
			tree[p].second=max(tree[ls(p)].second,tree[rs(p)].second);
			tree[p].cnt=tree[ls(p)].cnt+tree[rs(p)].cnt;
		}else if(tree[ls(p)].maxa>tree[rs(p)].maxa)
		{
			tree[p].second=max(tree[ls(p)].second,tree[rs(p)].maxa);
			tree[p].cnt=tree[ls(p)].cnt;
		}else
		{
			tree[p].second=max(tree[ls(p)].maxa,tree[rs(p)].second);
			tree[p].cnt=tree[rs(p)].cnt;
		}
	}
	void build(int p,int l,int r)
	{
		tree[p].l=l;tree[p].r=r;
		if(l==r)
		{
			tree[p].sum=a[l];
			tree[p].maxa=a[l];
			tree[p].maxb=a[l];
			tree[p].second=-inf;
			tree[p].cnt=1;
			return;
		}
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		push_up(p);
	}
	inline void fun(int p,int k1,int k2,int k3,int k4)
	{
		tree[p].sum+=k1*tree[p].cnt+k3*(tree[p].r-tree[p].l+1-tree[p].cnt);
		tree[p].maxb=max(tree[p].maxb,tree[p].maxa+k2);
		tree[p].add_b1=max(tree[p].add_b1,tree[p].add_a1+k2);
		tree[p].add_b2=max(tree[p].add_b2,tree[p].add_a2+k4);
		tree[p].maxa+=k1;
		tree[p].add_a1+=k1;
		tree[p].add_a2+=k3;
		if(tree[p].second!=-inf) tree[p].second+=k3;
	}
	inline void push_down(int p)
	{
		int maxn=max(tree[ls(p)].maxa,tree[rs(p)].maxa);
		if(tree[ls(p)].maxa==maxn) 
			fun(ls(p),tree[p].add_a1,tree[p].add_b1,tree[p].add_a2,tree[p].add_b2);
		else fun(ls(p),tree[p].add_a2,tree[p].add_b2,tree[p].add_a2,tree[p].add_b2);
		if(tree[rs(p)].maxb==maxn)
			fun(rs(p),tree[p].add_a1,tree[p].add_b1,tree[p].add_a2,tree[p].add_b2);
		else fun(rs(p),tree[p].add_a2,tree[p].add_b2,tree[p].add_a2,tree[p].add_b2);
		tree[p].add_a1=0;
		tree[p].add_a2=0;
		tree[p].add_b1=0;
		tree[p].add_b2=0;
	}
	void min_update(int p,int l,int r,int k)
	{
		if(tree[p].l>r||tree[p].r<l||k>=tree[p].maxa) return;
		if(l<=tree[p].l&&tree[p].r<=r&&k>tree[p].second)
		{
		    fun(p,k-tree[p].maxa,k-tree[p].maxa,0,0);
			return;
		}
		push_down(p);
		min_update(ls(p),l,r,k);
		min_update(rs(p),l,r,k);
		push_up(p);
	}
	void add_update(int p,int l,int r,int k)
	{
		if(tree[p].l>r||tree[p].r<l) return;
		if(l<=tree[p].l&&tree[p].r<=r)
		{
			fun(p,k,k,k,k);
			return;
		}
		push_down(p);
		add_update(ls(p),l,r,k);
		add_update(rs(p),l,r,k);
		push_up(p);
	}
	int query_sum(int p,int l,int r)
	{
		if(tree[p].l>r||tree[p].r<l) return 0;
		if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
		push_down(p);
		return query_sum(ls(p),l,r)+query_sum(rs(p),l,r);
	}
	int query_max1(int p,int l,int r)
	{
		if(tree[p].l>r||tree[p].r<l) return -inf;
		if(l<=tree[p].l&&tree[p].r<=r) return tree[p].maxa;
		push_down(p);
		return max(query_max1(ls(p),l,r),query_max1(rs(p),l,r));
	}
	int query_max2(int p,int l,int r)
	{
		if(tree[p].l>r||tree[p].r<l) return -inf;
		if(l<=tree[p].l&&tree[p].r<=r) return tree[p].maxb;
		push_down(p);
		return max(query_max2(ls(p),l,r),query_max2(rs(p),l,r));
	}
} st;
int n,m;
signed main()
{
	n=read();m=read();
	for(R int i=1;i<=n;i++)
		a[i]=read();
	st.build(1,1,n);
	for(R int i=1;i<=m;i++)
	{
		int op=read(),l,r,k;
		switch(op)
		{
			case 1:
				l=read();r=read();k=read();
				st.add_update(1,l,r,k);
				break;
			case 2:
				l=read();r=read();k=read();
				st.min_update(1,l,r,k);
				break;
			case 3:
				l=read();r=read();
				printf("%lld\n",st.query_sum(1,l,r));
				break;
			case 4:
				l=read();r=read();
				printf("%lld\n",st.query_max1(1,l,r));
				break;
			case 5:
				l=read();r=read();
				printf("%lld\n",st.query_max2(1,l,r));
				break;
		}
	}
	return 0;
}