#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=500005;
int n,m,op,l,r;ll a[M],v;
ll tag1[M<<3],tag2[M<<3];
//tag1->add tag  tag2->add tag max bf pd
ll tag3[M<<3],tag4[M<<3];
//tag3->maxn add tag  tag4->maxn add tag max bf pd
ll maxn[M<<3],smaxn[M<<3];
//maxn->maxn  smaxn->se maxn
ll bmaxn[M<<3];
//bmaxn->b max
int cnt[M<<3];
//cnt->maxn count
ll sum[M<<3];
void print(int x,int l,int r){
	printf("l=%d r=%d\n",l,r);
	printf("sum=%lld\n",sum[x]);
	printf("tag1=%lld tag2=%lld tag3=%lld tag4=%lld\n",tag1[x],tag2[x],tag3[x],tag4[x]);
	printf("sem=%lld maxn=%lld maxnb=%lld cnt=%d\n",smaxn[x]<-1e15?-2000000000:smaxn[x],maxn[x],bmaxn[x],cnt[x]);
}
inline void pushup(int x,int l,int r){
//	print(x,l,r);
    sum[x]=sum[x<<1]+sum[x<<1|1];
    maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
    bmaxn[x]=max(bmaxn[x<<1],bmaxn[x<<1|1]);
    smaxn[x]=-1e18;cnt[x]=0;
    if(maxn[x]==maxn[x<<1]) cnt[x]=cnt[x<<1];
    else smaxn[x]=maxn[x<<1];
    if(maxn[x]==maxn[x<<1|1]) cnt[x]+=cnt[x<<1|1];
    else smaxn[x]=maxn[x<<1|1];
    smaxn[x]=max(smaxn[x],max(smaxn[x<<1],smaxn[x<<1|1]));
//    print(x,l,r);
//    printf("--------\n");
}
void build(int x,int l,int r){
    if(l==r){
        sum[x]=maxn[x]=bmaxn[x]=a[l];
        smaxn[x]=-1e18;cnt[x]=1;
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x,l,r);
}
void add_tag(int x,int l,int r,ll t1,ll t2,ll t3,ll t4){
    bmaxn[x]=max(bmaxn[x],maxn[x]+t4);
    maxn[x]+=t3;
    sum[x]+=(r-l+1-cnt[x])*t1+cnt[x]*t3;
    smaxn[x]+=t1;
    tag2[x]=max(tag2[x],tag1[x]+t2);
    tag1[x]+=t1;
    tag4[x]=max(tag4[x],tag3[x]+t4);
    tag3[x]+=t3;
}
inline void pushdown(int x,int l,int r){
//	print(x,l,r);
    int mid=l+r>>1;
//    print(x<<1,l,mid);
//    print(x<<1|1,mid+1,r);
//    printf("-----\n");
    bool b1=maxn[x<<1]>=maxn[x<<1|1];
    bool b2=maxn[x<<1|1]>=maxn[x<<1];
    if(b1) add_tag(x<<1,l,mid,tag1[x],tag2[x],tag3[x],tag4[x]);
    else add_tag(x<<1,l,mid,tag1[x],tag2[x],tag1[x],tag2[x]);
    if(b2) add_tag(x<<1|1,mid+1,r,tag1[x],tag2[x],tag3[x],tag4[x]);
    else add_tag(x<<1|1,mid+1,r,tag1[x],tag2[x],tag1[x],tag2[x]);
    tag1[x]=tag2[x]=tag3[x]=tag4[x]=0;
//    print(x<<1,l,mid);
//    print(x<<1|1,mid+1,r);
//    printf("------------%d %d\n",b1,b2);
}
void modify_add(int x,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){
//    	print(x,l,r);
        tag1[x]+=v;tag3[x]+=v;
        tag2[x]=max(tag1[x],tag2[x]);
        tag4[x]=max(tag3[x],tag4[x]);
        sum[x]+=(r-l+1)*v;
        maxn[x]+=v;smaxn[x]+=v;
        bmaxn[x]=max(bmaxn[x],maxn[x]);
//        print(x,l,r);
        return;
    }
    pushdown(x,l,r);
    int mid=l+r>>1;
    if(ql<=mid) modify_add(x<<1,l,mid,ql,qr,v);
    if(qr>mid) modify_add(x<<1|1,mid+1,r,ql,qr,v);
    pushup(x,l,r);
}
void modify_min(int x,int l,int r,int ql,int qr,ll v){
    if(v>=maxn[x]) return;
    if(ql<=l&&r<=qr&&smaxn[x]<v){
//    	printf("!!!");
//    	print(x,l,r);
        sum[x]+=cnt[x]*(v-maxn[x]);
        tag3[x]+=v-maxn[x];
        maxn[x]=v;
//        print(x,l,r);
        return;
    }
    pushdown(x,l,r);
    int mid=l+r>>1;
    if(ql<=mid) modify_min(x<<1,l,mid,ql,qr,v);
    if(qr>mid) modify_min(x<<1|1,mid+1,r,ql,qr,v);
    pushup(x,l,r);
}
ll query_sum(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[x];
    pushdown(x,l,r);
    int mid=l+r>>1;ll res=0;
    if(ql<=mid) res=query_sum(x<<1,l,mid,ql,qr);
    if(qr>mid) res+=query_sum(x<<1|1,mid+1,r,ql,qr);
    return res;
}
ll query_amax(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return maxn[x];
    pushdown(x,l,r);
    int mid=l+r>>1;ll res=0;
    if(ql<=mid) res=query_amax(x<<1,l,mid,ql,qr);
    if(qr>mid) res=max(res,query_amax(x<<1|1,mid+1,r,ql,qr));
    return res;
}
ll query_bmax(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return bmaxn[x];
    pushdown(x,l,r);
    int mid=l+r>>1;ll res=0;
    if(ql<=mid) res=query_bmax(x<<1,l,mid,ql,qr);
    if(qr>mid) res=max(res,query_bmax(x<<1|1,mid+1,r,ql,qr));
    return res;
}
ll res,f;char ch;
inline ll read(){
	res=0;f=1;ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+(ch&15);
		ch=getchar();
	}
	return f==1?res:-res;
}
void printt(ll x){
	if(x==0) return;
	printt(x/10);
	putchar(x%10+'0');
}
void print(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x==0) putchar('0');
	else printt(x);
	putchar('\n');
}
int main(){
//	freopen("P6242_1.in","r",stdin);
//	freopen("111.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    while(m--){
        op=read();
        switch(op){
            case 1:{
                l=read(),r=read(),v=read();
                modify_add(1,1,n,l,r,v);
                break;
            }
            case 2:{
                l=read(),r=read(),v=read();
                modify_min(1,1,n,l,r,v);
                break;
            }
            case 3:{
                l=read(),r=read();
                print(query_sum(1,1,n,l,r));
                break;
            }
            case 4:{
                l=read(),r=read();
                print(query_amax(1,1,n,l,r));
                break;
            }
            case 5:{
                l=read(),r=read();
                print(query_bmax(1,1,n,l,r));
                break;
            }
        }
//        printf("**********\n");
    }
    return 0;
}

tag1 是非最大值的加标记，tag2 是非最大值在下放前加标记的最大值，tag3 是最大值的加标记，tag4 是最大值在下放前加标记的最大值，maxn 是最大值，smaxn 是次大值，bmaxn 是历史最大值，cnt 是最大值的数量