//
// Created by 15411 on 2024/3/15.
//
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define lc p<<1
#define rc (p<<1|1)
using namespace std;
const int N=5e5+7;
ll n,m;
ll a[N];
/*-------------------------------------------------------------------------------------------------------------------*/
struct node{
    ll l,r;
    ll max0,ma,se,t;
    ll sum,change;
    bool vstMin;
}tree[N<<3];
void pushUp(ll p){
    //更新区间和
    tree[p].sum=tree[lc].sum+tree[rc].sum;
    //更新最大最值
    tree[p].ma=max(tree[lc].ma,tree[rc].ma);
    tree[p].t=0;
    if(tree[lc].ma==tree[p].ma)tree[p].t+=tree[lc].t;
    if(tree[rc].ma==tree[p].ma)tree[p].t+=tree[rc].t;
    //更新次大值
    tree[p].se=-1*1e12;
    if(tree[lc].ma!=tree[p].ma&&tree[lc].ma>tree[p].se)tree[p].se=tree[lc].ma;
    if(tree[lc].se!=tree[p].ma&&tree[lc].se>tree[p].se)tree[p].se=tree[lc].se;
    if(tree[rc].ma!=tree[p].ma&&tree[rc].ma>tree[p].se)tree[p].se=tree[rc].ma;
    if(tree[rc].se!=tree[p].ma&&tree[rc].se>tree[p].se)tree[p].se=tree[rc].se;
    //更新历史最大值
    tree[p].max0=max(tree[p].max0,tree[p].ma);
}
void build(ll p,ll l,ll r){
    tree[p].l=l,tree[p].r=r,tree[p].change=0;tree[p].max0=0;tree[p].vstMin=false;
    if(l==r){
        tree[p].max0=a[l];tree[p].ma=a[l]; tree[p].sum=a[l];
        tree[p].t=1;
        tree[p].se=-1*1e12;
        return;
    }
    ll mid=(tree[p].l+tree[p].r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushUp(p);
}
void pushDown(ll p);
void addTagAdd(ll p,ll k){
    if(tree[p].vstMin)pushDown(p);
    tree[p].sum=tree[p].sum+k*(tree[p].r-tree[p].l+1);
    tree[p].ma+=k;tree[p].se+=k;
    tree[p].max0=max(tree[p].max0,tree[p].ma);
    if(tree[p].l!=tree[p].r)tree[p].change+=k;
}
void addTagMin(ll p,ll v){
    if(tree[p].change)pushDown(p);
    if(tree[p].ma<=v)return;
    tree[p].sum=tree[p].sum-(tree[p].ma-v)*tree[p].t;
    tree[p].ma=v;
    if(tree[p].l!=tree[p].r)tree[p].vstMin=true;
}
void pushDown(ll p){
    if(tree[p].change!=0){
        addTagAdd(lc,tree[p].change);
        addTagAdd(rc,tree[p].change);
        tree[p].change=0;
    }
    if(tree[p].vstMin){
        addTagMin(lc,tree[p].ma);
        addTagMin(rc,tree[p].ma);
        tree[p].vstMin=false;
    }
}
void updateAdd(ll p,ll L,ll R,ll k){
    if(L<=tree[p].l&&tree[p].r<=R){
        addTagAdd(p,k);
        return;
    }
    pushDown(p);
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=L)updateAdd(lc,L,R,k);
    if(mid+1<=R)updateAdd(rc,L,R,k);
    pushUp(p);
}
void updateMin(ll p,ll L,ll R,ll v){
    if(L<=tree[p].l&&tree[p].r<=R){
        if(tree[p].ma<=v)return;
        if(tree[p].se<v){
            addTagMin(p,v);
            return;
        }
    }
    pushDown(p);
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=L)updateMin(lc,L,R,v);
    if(mid+1<=R)updateMin(rc,L,R,v);
    pushUp(p);
}
ll querySum(ll p,ll L,ll R){
    if(L<=tree[p].l&&tree[p].r<=R){
        return tree[p].sum;
    }
    pushDown(p);
    ll ret=0;
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=L)ret+= querySum(lc,L,R);
    if(mid+1<=R)ret+= querySum(rc,L,R);
    return ret;
}
ll queryMax0(ll p,ll L,ll R){
    if(L<=tree[p].l&&tree[p].r<=R){
        return tree[p].max0;
    }
    pushDown(p);
    ll ret=-1*1e12;
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=L)ret=max(ret,queryMax0(lc,L,R));
    if(mid+1<=R)ret=max(ret,queryMax0(rc,L,R));
    return ret;
}
ll queryMa(ll p,ll L,ll R){
    if(L<=tree[p].l&&tree[p].r<=R){
        return tree[p].ma;
    }
    pushDown(p);
    ll ret=-1*1e12;
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=L)ret=max(ret,queryMa(lc,L,R));
    if(mid+1<=R)ret=max(ret,queryMa(rc,L,R));
    return ret;
}
/*-------------------------------------------------------------------------------------------------------------------*/
void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    ll op,l,r,v,k,ans;
    while(m--){
        cin>>op>>l>>r;/*
        if(op==0)op=2;
        else if(op==1)op=4;
        else if(op==2)op=3;*/
        if(op==1){
            cin>>k;updateAdd(1,l,r,k);
        }
        else if(op==2){
            cin>>v;updateMin(1,l,r,v);
        }
        else if(op==3){
            ans= querySum(1,l,r);cout<<ans<<endl;
        }
        else if(op==4){
            ans= queryMa(1,l,r);cout<<ans<<endl;
        }
        else if(op==5){
            ans= queryMax0(1,l,r);cout<<ans<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //ll t;cin>>t;while(t--)
        solve();
    return 0;
}