#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const long long INF=1e18;
struct tree{
    long long l,r;
    long long sum,add,ake;
}q[N*4+10],b[N*4+10];
long long n,m;
long long a[N];
void pushdown(long long p){
    if(q[p].add){
        q[p*2].sum += (q[p*2].r-q[p*2].l+1)*q[p].add;
        q[p*2].add += q[p].add;
        q[p*2].ake += q[p].add;
        q[p*2+1].sum += (q[p*2+1].r-q[p*2+1].l+1)*q[p].add;
        q[p*2+1].add += q[p].add;
        q[p*2+1].ake += q[p].add;
        b[p*2].ake = max(b[p*2].ake, q[p*2].ake);
        b[p*2+1].ake = max(b[p*2+1].ake, q[p*2+1].ake);
        q[p].add=0;
    }
}
void build(long long p,long long l,long long r){
    q[p].l=l, q[p].r=r;
    b[p].l=l, b[p].r=r;
    if(l==r){
        q[p].sum=a[l];
        q[p].ake=a[l];
        b[p].ake=a[l];
        return;
    }
    long long mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    q[p].sum=q[p*2].sum+q[p*2+1].sum;
    q[p].ake=max(q[p*2].ake,q[p*2+1].ake);
    b[p].ake=max(b[p*2].ake,b[p*2+1].ake);
}
void change(long long p,long long x,long long y,long long z){
    if(x<=q[p].l && y>=q[p].r){
        q[p].sum += (q[p].r-q[p].l+1)*z;
        q[p].add += z;
        q[p].ake += z;
        b[p].ake = max(b[p].ake, q[p].ake);
        return;
    }
    pushdown(p);
    long long mid=(q[p].l+q[p].r)/2;
    if(x<=mid) change(p*2,x,y,z);
    if(y>mid) change(p*2+1,x,y,z);
    q[p].sum=q[p*2].sum+q[p*2+1].sum;
    q[p].ake=max(q[p*2].ake,q[p*2+1].ake);
    b[p].ake=max(b[p*2].ake,b[p*2+1].ake);
}
long long find(long long p,long long x,long long y){
    if(x<=q[p].l && y>=q[p].r) return q[p].sum;
    pushdown(p);
    long long ans=0;
    long long mid=(q[p].l+q[p].r)/2;
    if(x<=mid) ans+=find(p*2,x,y);
    if(y>mid) ans+=find(p*2+1,x,y);
    return ans;
}
void chan(long long p,long long x,long long y,long long z){
    if(q[p].ake<z) return;
    if(q[p].l==q[p].r){
        q[p].sum=min(q[p].sum,z);
        q[p].ake=q[p].sum;
        return;
    }
    pushdown(p);
    long long mid=(q[p].l+q[p].r)/2;
    if(x<=mid) chan(p*2,x,y,z);
    if(y>mid) chan(p*2+1,x,y,z);
    q[p].sum=q[p*2].sum+q[p*2+1].sum;
    q[p].ake=max(q[p*2].ake,q[p*2+1].ake);
}

long long ma_x(long long p,long long x,long long y){
    if(x<=q[p].l && y>=q[p].r) return q[p].ake;
    pushdown(p);
    long long ans=-INF;
    long long mid=(q[p].l+q[p].r)/2;
    if(x<=mid) ans=max(ans,ma_x(p*2,x,y));
    if(y>mid) ans=max(ans,ma_x(p*2+1,x,y));
    return ans;
}
long long ma_y(long long p,long long x,long long y){
    if(x<=b[p].l && y>=b[p].r) return b[p].ake;
    long long ans=-INF;
    long long mid=(b[p].l+b[p].r)/2;
    if(x<=mid) ans=max(ans,ma_y(p*2,x,y));
    if(y>mid) ans=max(ans,ma_y(p*2+1,x,y));
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        long long w,x,y,z;
        cin>>w;
        if(w==1){
            cin>>x>>y>>z;
            change(1,x,y,z);
        }
        else if(w==2){
            cin>>x>>y>>z;
            chan(1,x,y,z);
        }
        else if(w==3){
            cin>>x>>y;
            cout<<find(1,x,y)<<endl;
        }
        else if(w==4){
            cin>>x>>y;
            cout<<ma_x(1,x,y)<<endl;
        }
        else if(w==5){
            cin>>x>>y;
            cout<<ma_y(1,x,y)<<endl;
        }
    }
    return 0;
}