#include<bits/stdc++.h>
using namespace std;
/*
tag1：该区间最大值的懒标记。
tag2：该区间非最大值的懒标记。
tag3：该区间最大值的懒标记的最大值。
tag4：该区间非最大的值的懒标记的最大值。
*/
#define int long long
#define p2 p<<1
#define p3 p<<1|1
const int N=5e5+10;
struct node{
	int l,r;
	int sum,maxa,maxb,cnt,s;
	int tag1,tag2,tag3,tag4;
}tr[N<<2];
int n,m,aa[N];
void L(int p,int a,int b,int c,int d){
	tr[p].sum+=a*tr[p].cnt+b*(tr[p].r-tr[p].l+1-tr[p].cnt);
	tr[p].maxb=max(tr[p].maxb,tr[p].maxa+c);
	tr[p].maxa+=a;
	if(tr[p].s!=-2e9) tr[p].s+=b;
	tr[p].tag3=max(tr[p].tag3,tr[p].tag1+c);
	tr[p].tag4=max(tr[p].tag4,tr[p].tag2+d);
	tr[p].tag1+=a,tr[p].tag2+=b;
}
void push_up(int p){
	tr[p].sum=tr[p2].sum+tr[p3].sum;
	tr[p].maxa=max(tr[p2].maxa,tr[p3].maxa);
	tr[p].maxb=max(tr[p2].maxb,tr[p3].maxb);
	if(tr[p2].maxa==tr[p3].maxa){
		tr[p].s=max(tr[p2].s,tr[p3].s);
		tr[p].cnt=tr[p2].cnt+tr[p3].cnt;
	}	
	else if(tr[p2].maxa>tr[p3].maxa){
		tr[p].s=max(tr[p2].s,tr[p3].maxa);
		tr[p].cnt=tr[p2].cnt;
	}
	else {
		tr[p].s=max(tr[p3].s,tr[p2].maxa);
		tr[p].cnt=tr[p3].cnt;
	}
}
void push_down(int p){
	int maxn=max(tr[p*2].maxa,tr[p*2+1].maxa);
	if(tr[p*2].maxa==maxn) L(p*2,tr[p].tag1,tr[p].tag2,tr[p].tag3,tr[p].tag4);
	else L(p*2,tr[p].tag2,tr[p].tag2,tr[p].tag4,tr[p].tag4);
	if(tr[p*2+1].maxa==maxn) L(p*2+1,tr[p].tag1,tr[p].tag2,tr[p].tag3,tr[p].tag4);
	else L(p*2+1,tr[p].tag2,tr[p].tag2,tr[p].tag4,tr[p].tag4);
	tr[p].tag1=tr[p].tag2=tr[p].tag3=tr[p].tag4=0;
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].cnt=1;
		tr[p].s=-2e9;
		tr[p].maxa=tr[p].maxb=tr[p].sum=aa[l];
		return;
	}
	int mid=l+r>>1;
	build(p2,l,mid);
	build(p3,mid+1,r);
	push_up(p);
}
void upd(int p,int x,int y,int k){
	if(tr[p].l>=x&&tr[p].r<=y){
		tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
		tr[p].maxa+=k;
		tr[p].maxb=max(tr[p].maxa,tr[p].maxb);
		if(tr[p].s!=-2e9) tr[p].s+=k;
		tr[p].tag1+=k,tr[p].tag2+=k;
		tr[p].tag3=max(tr[p].tag3,tr[p].tag1);
		tr[p].tag4=max(tr[p].tag4,tr[p].tag2);
		return;
	}
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid) upd(p2,x,y,k);
	if(y>mid) upd(p3,x,y,k);
	push_up(p);
}
void updm(int p,int x,int y,int k){
	if(tr[p].l>=x&&tr[p].r<=y&&tr[p].s<k){
		tr[p].sum-=tr[p].cnt*(tr[p].maxa-k);
		tr[p].maxa=k,tr[p].tag1-=tr[p].maxa-k;
		return;
	}
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid) updm(p2,x,y,k);
	if(y>mid) updm(p3,x,y,k);
	push_up(p);
}
int queryA(int p,int x,int y){
	if(tr[p].l>=x&&tr[p].r<=y) return tr[p].maxa;
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1,ret=0;
	if(x<=mid) ret=queryA(p2,x,y);
	if(y>mid) ret=max(ret,queryA(p3,x,y));
	return ret;
}
int queryB(int p,int x,int y){
	if(tr[p].l>=x&&tr[p].r<=y) return tr[p].maxb;
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1,ret=0;
	if(x<=mid) ret=queryB(p2,x,y);
	if(y>mid) ret=max(ret,queryB(p3,x,y));
	return ret;
}
int query(int p,int x,int y){
	if(tr[p].l>=x&&tr[p].r<=y) return tr[p].sum;
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1,ret=0;
	if(x<=mid) ret=query(p2,x,y);
	if(y>mid) ret+=query(p3,x,y);
	return ret;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>aa[i];
	build(1,1,n);
	while(m--){
		int opt,l,r,k;
		cin>>opt>>l>>r;
		if(opt==1) cin>>k,upd(1,l,r,k);
		else if(opt==2) cin>>k,updm(1,l,r,k);
		else if(opt==3) cout<<query(1,l,r)<<'\n';
		else if(opt==4) cout<<queryA(1,l,r)<<'\n';
		else cout<<queryB(1,l,r)<<'\n';
	}
	return 0;
}