#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
namespace IO{
    template<typename T> inline static void read(T &x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f==-1) x=-x;}
    template<typename T,typename ...Args> inline static void read(T& x,Args& ...args){read(x);read(args...);}
    template<typename T> inline static void write(char c,T x){T p=x;if(!p) putchar('0');if(p<0){putchar('-');p=-p;}int cnt[105],tot=0;while(p){cnt[++tot]=p%10;p/=10;}for(int i=tot;i>=1;i--){putchar(cnt[i]+'0');}putchar(c);}
    template<typename T,typename ...Args> inline static void write(const char c,T x,Args ...args){write(c,x);write(c,args...);}
}using namespace IO;
#define LL long long
#define ls p<<1
#define rs p<<1|1
const int N=5e5+10;
const int INF=2e9+7;
int n,m;
int a[N],op,l,r,k;
struct seg{
    LL sum;
    int l,r,maxa,maxb,cnt,se;
    int add1,add2,add3,add4;
}t[N<<2];
inline void pushup(int p){
    t[p].sum=t[ls].sum+t[rs].sum;
    t[p].maxa=max(t[ls].maxa,t[rs].maxa);
    t[p].maxb=max(t[ls].maxb,t[rs].maxb);
    if(t[ls].maxa==t[rs].maxa){
        t[p].se=max(t[ls].se,t[rs].se);
        t[p].cnt=t[ls].cnt+t[rs].cnt;
    }else if(t[ls].maxa>t[rs].maxa){
         t[p].se=max(t[ls].se,t[rs].maxa);
         t[p].cnt=t[ls].cnt;
    }else{
        t[p].se=max(t[ls].maxa,t[rs].se);
        t[p].cnt=t[rs].cnt;
    }
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].sum=1ll*a[l];
        t[p].maxa=t[p].maxb=a[l];
        t[p].cnt=1,t[p].se=-INF;
        return ;
    }int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(p);
}
inline void change(int p,int k1,int k2,int k3,int k4){
    t[p].sum+=1ll*k1*t[p].cnt+1ll*k2*(t[p].r-t[p].l+1-t[p].cnt);
    t[p].maxb=max(t[p].maxb,t[p].maxa+k3),t[p].maxa+=k1;
    if(t[p].se!=-INF) t[p].se+=k2;
    t[p].add3=max(t[p].add3,t[p].add1+k3),t[p].add4=max(t[p].add4,t[p].add2+k4);
    t[p].add1+=k1,t[p].add2+=k2;
}
inline void pushdown(int p){
    int maxx=max(t[ls].maxa,t[rs].maxa);
    if(t[ls].maxa==maxx)change(ls,t[p].add1,t[p].add2,t[p].add3,t[p].add4);
    else change(ls,t[p].add2,t[p].add2,t[p].add4,t[p].add4);
    if(t[rs].maxa==maxx)change(rs,t[p].add1,t[p].add2,t[p].add3,t[p].add4);
    else change(rs,t[p].add2,t[p].add2,t[p].add4,t[p].add4);
    t[p].add1=t[p].add2=t[p].add3=t[p].add4=0;
}
void update_add(int p,int l,int r,int k){
    if(l>t[p].r||r<t[p].l) return;
    if(l<=t[p].l&&t[p].r<=r){
        t[p].sum+=1ll*k*(t[p].r-t[p].l+1);
        t[p].maxa+=k,t[p].maxb=max(t[p].maxb,t[p].maxa);
        if(t[p].se!=-INF) t[p].se+=k;
        t[p].add1+=k,t[p].add2+=k;
        t[p].add3=max(t[p].add3,t[p].add1),t[p].add4=max(t[p].add4,t[p].add2);
        return ;
    }pushdown(p);
    update_add(ls,l,r,k),update_add(rs,l,r,k);
    pushup(p);
}
void update_min(int p,int l,int r,int k){
    if(l>t[p].r||r<t[p].l||k>=t[p].maxa) return ;
    if(l<=t[p].r&&t[p].r<=r&&k>t[p].se){
        int tmp=t[p].maxa-k;
        t[p].sum-=1ll*t[p].cnt*tmp;
        t[p].maxa=k,t[p].add1-=tmp;
        return ;
    }pushdown(p);
    update_min(ls,l,r,k),update_min(rs,l,r,k);
    pushup(p);
}
LL query_sum(int p,int l,int r){
    if(l>t[p].r||r<t[p].l) return 0;
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    pushdown(p);
    return query_sum(ls,l,r)+query_sum(rs,l,r);
}
int query_max1(int p,int l,int r){
    if(l>t[p].r||r<t[p].l) return -INF;
    if(l<=t[p].l&&t[p].r<=r) return t[p].maxa;
    pushdown(p);
    return max(query_max1(ls,l,r),query_max1(rs,l,r));
}
int query_max2(int p,int l,int r){
    if(l>t[p].r||r<t[p].l) return -INF;
    if(l<=t[p].l&&t[p].r<=r) return t[p].maxb;
    pushdown(p);
    return max(query_max2(ls,l,r),query_max2(rs,l,r));
}
int main(){
    read(n,m);
    for(int i=1;i<=n;++i) read(a[i]);
    build(1,1,n);
    while(m--){
        read(op,l,r);
        if(op==1) read(k),update_add(1,l,r,k);
        if(op==2) read(k),update_min(1,l,r,k);
        if(op==3) write('\n',query_sum(1,l,r));
        if(op==4) write('\n',query_max1(1,l,r));
        if(op==5) write('\n',query_max2(1,l,r));
    }
    return 0;
}