#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
using ll=long long;
ll nums[N+1],sum[4*N],rangeMax[4*N],subMax[4*N],maxCnt[4*N],historyMax[4*N],maxAdd[4*N],otherAdd[4*N],maxAddTop[4*N],otherAddTop[4*N];
void up(int i){
    int l=2*i,r=l+1;
    sum[i]=sum[l]+sum[r];
    historyMax[i]=max(historyMax[l],historyMax[r]);
    rangeMax[i]=max(rangeMax[l],rangeMax[r]);
    if(rangeMax[l]==rangeMax[r]){
        subMax[i]=max(subMax[l],subMax[r]);
        maxCnt[i]=maxCnt[l]+maxCnt[r];
    }else if(rangeMax[l]>rangeMax[r]){
        subMax[i]=max(subMax[l],rangeMax[r]);
        maxCnt[i]=maxCnt[l];
    }else{
        subMax[i]=max(subMax[r],rangeMax[l]);
        maxCnt[i]=maxCnt[r];
    }
}
void build(int l,int r,int i){
    if(l==r){
        historyMax[i]=rangeMax[i]=sum[i]=nums[l];
        subMax[i]=INT64_MIN;
        maxCnt[i]=1;
        maxAddTop[i]=otherAddTop[i]=otherAdd[i]=maxAdd[i]=0;
    }else{
        int mid=(l+r)/2;
        build(l,mid,2*i);
        build(mid+1,r,2*i+1);
        up(i);
    }
}
void lazy(int i,int cnt,ll maxAddVal,ll otherAddVal,ll maxUpVal,ll otherUpVal){
    historyMax[i]=max(historyMax[i],rangeMax[i]+maxUpVal);
    maxAddTop[i]=max(maxAddTop[i],maxAdd[i]+maxUpVal);
    otherAddTop[i]=max(otherAddTop[i],otherAdd[i]+otherUpVal);
    sum[i]+=maxAddVal*maxCnt[i]+otherAddVal*(cnt-maxCnt[i]);
    rangeMax[i]+=maxAddVal;
    subMax[i]+=(subMax[i]==INT64_MIN)?0:otherAddVal;
    maxAdd[i]+=maxAddVal;
    otherAdd[i]+=otherAddVal;
}
void down(int i,int lCnt,int rCnt){
    int l=2*i,r=l+1;
    ll temp=max(rangeMax[l],rangeMax[r]);
    if(temp==rangeMax[l]){
        lazy(l,lCnt,maxAdd[i],otherAdd[i],maxAddTop[i],otherAddTop[i]);
    }else{
        lazy(l,lCnt,otherAdd[i],otherAdd[i],otherAddTop[i],otherAddTop[i]);
    }
    if(temp==rangeMax[r]){
        lazy(r,rCnt,maxAdd[i],otherAdd[i],maxAddTop[i],otherAddTop[i]);
    }else{
        lazy(r,rCnt,otherAdd[i],otherAdd[i],otherAddTop[i],otherAddTop[i]);
    }
    maxAdd[i]=otherAdd[i]=maxAddTop[i]=otherAddTop[i]=0;
}
ll querySum(const int jobL,const int jobR,int l,int r,int i){
    if(jobL<=l&&r<=jobR){
        return sum[i];
    }
    
    ll ans=0;
    int mid=(l+r)/2;
    down(i,mid-l+1,r-(mid+1)+1);
    if(jobL<=mid){
        ans+=querySum(jobL,jobR,l,mid,2*i);
    }
    if(jobR>mid){
        ans+=querySum(jobL,jobR,mid+1,r,2*i+1);
    }
    return ans;
}
ll queryMax(const int jobL,const int jobR,const int pattern,int l,int r,int i){
    if(jobL<=l&&r<=jobR){
        return (pattern==0)?historyMax[i]:rangeMax[i];
    }
    
    int mid=(l+r)/2;
    ll ans=INT64_MIN;
    down(i,mid-l+1,r-(mid+1)+1);
    if(jobL<=mid){
        ans=max(ans,queryMax(jobL,jobR,pattern,l,mid,2*i));
    }
    if(jobR>mid){
        ans=max(ans,queryMax(jobL,jobR,pattern,mid+1,r,2*i+1));
    }
    return ans;
}
void add(const int jobL,const int jobR,const ll jobVal,int l,int r,int i){
    if(jobL<=l&&r<=jobR){
        lazy(i,r-l+1,jobVal,jobVal,0,0);
    }else{
        int mid=(l+r)/2;
        down(i,mid-l+1,r-(mid+1)+1);
        if(jobL<=mid){
            add(jobL,jobR,jobVal,l,mid,2*i);
        }
        if(jobR>mid){
            add(jobL,jobR,jobVal,mid+1,r,2*i+1);
        }
        up(i);
    }
}
void setMin(const int jobL,const int jobR,const ll jobVal,int l,int r,int i){
    if(jobVal>=rangeMax[i]){
        return;
    }
    if(jobL<=l&&r<=jobR&&jobVal>=subMax[i]){
        lazy(i,r-l+1,jobVal-rangeMax[i],0,0,0);
    }else{
        int mid=(l+r)/2;
        down(i,mid-l+1,r-(mid+1)+1);
        if(jobL<=mid){
            setMin(jobL,jobR,jobVal,l,mid,2*i);
        }
        if(jobR>mid){
            setMin(jobL,jobR,jobVal,mid+1,r,2*i+1);
        }
        up(i);
    }
}
int main(){
    int n,m,op,l,r;
    ll k,v;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>nums[i];
    }
    build(1,n,1);
    while(m--){
        cin>>op>>l>>r;
        switch(op){
            case 1:
                cin>>k;
                add(l,r,k,1,n,1);
                break;
            case 2:
                cin>>v;
                setMin(l,r,v,1,n,1);
                break;
            case 3:
                cout<<querySum(l,r,1,n,1)<<endl;
                break;
            case 4:
                cout<<queryMax(l,r,1,1,n,1)<<endl;
                break;
            case 5:
                cout<<queryMax(l,r,0,1,n,1)<<endl;
                break;    
            default:
                break;
        }
    }
    
    
    return 0;
}