#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5,inf=1e9;
bool ST;
int n,m,O[N],L[N],R[N];
ll a[N],V[N];
struct line{
    ll k,b;
    bool operator<(line t)const{return b==t.b?k<t.k:b<t.b;}
    void upd(int x){b+=k*x;}
};
ll calc(line x,line y) {
    if(x.k>=y.k)return inf;
    return (x.b-y.b)/(y.k-x.k);
}
struct tree{int l,r,ad,ok;ll s0,tg,lv,rv,s,lim;line mx;}t[N<<2];
void Ad(int p,int k){t[p].rv+=1ll*k*t[p].r,t[p].lv+=1ll*k*t[p].l,t[p].s+=t[p].s0*k,t[p].mx.upd(k),t[p].ad+=k;}
void Md(int p,ll k){t[p].tg=t[p].lv=t[p].rv=k,t[p].s=(t[p].r-t[p].l+1)*k,t[p].mx={t[p].r,k},t[p].lim=inf,t[p].ad=0;}
void down(int p) {
    if(~t[p].tg)Md(p<<1,t[p].tg),Md(p<<1|1,t[p].tg),t[p].tg=-1;
    if(t[p].ad)Ad(p<<1,t[p].ad),Ad(p<<1|1,t[p].ad),t[p].ad=0;
}
void upd(int p) {
    t[p].s=t[p<<1].s+t[p<<1|1].s,t[p].lv=t[p<<1].lv,t[p].rv=t[p<<1|1].rv;
    t[p].ok=(t[p<<1].ok&t[p<<1|1].ok&(t[p<<1].rv<=t[p<<1|1].lv));
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx),t[p].lim=min(t[p<<1].lim,t[p<<1|1].lim);
    t[p].lim=min(t[p].lim,min(calc(t[p].mx,t[p<<1].mx),calc(t[p].mx,t[p<<1|1].mx)));
}
void build(int p,int l,int r) {
    t[p]={l,r,0,0,1ll*(l+r)*(r-l+1)/2,-1};
    if(l==r)return t[p].s=t[p].lv=t[p].rv=a[l],t[p].lim=inf,t[p].mx={l,a[l]},t[p].ok=1,void();
    int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r),upd(p);
}
void mdf(int p,ll v) {
    if(t[p].rv<=v)return;
    if(t[p].lv>=v)return Md(p,v);
    down(p),mdf(p<<1,v),mdf(p<<1|1,v),upd(p);
}
void Mdf(int p,ll v) {
    if(t[p].mx.b<=v)return;
    if(t[p].ok)return mdf(p,v);
    down(p),Mdf(p<<1,v),Mdf(p<<1|1,v),upd(p);
}
void Add(int p) {
    if(t[p].lim>1)return Ad(p,1);
    down(p),Add(p<<1),Add(p<<1|1),upd(p);
}
ll qry(int p,int l,int r) {
    if(t[p].l>=l&&t[p].r<=r)return t[p].s;
    int mid=t[p].l+t[p].r>>1;ll s=0;down(p);
    if(l<=mid)s=qry(p<<1,l,r);
    if(r>mid)s+=qry(p<<1|1,l,r);
    return s;
} 
namespace sub{
    struct tree{int l,r,ct;ll tg,mx,sec,s;}t[N<<2];
    void Md(int p,ll k){if(t[p].mx>k)t[p].s+=t[p].ct*(k-t[p].mx),t[p].tg=t[p].mx=k;}
    void down(int p){if(~t[p].tg)Md(p<<1,t[p].tg),Md(p<<1|1,t[p].tg),t[p].tg=-1;}
    void upd(int p) {
        t[p].s=t[p<<1].s+t[p<<1|1].s,t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
        t[p].sec=max((t[p<<1].mx==t[p].mx?t[p<<1].sec:t[p<<1].mx),(t[p<<1|1].mx==t[p].mx?t[p<<1|1].sec:t[p<<1|1].mx));
        t[p].ct=(t[p<<1].mx==t[p].mx)*t[p<<1].ct+(t[p<<1|1].mx==t[p].mx)*t[p<<1|1].ct;
    }
    void build(int p,int l,int r) {
        t[p]={l,r,0,-1};
        if(l==r)return t[p].s=t[p].mx=a[l],t[p].sec=-1,t[p].ct=1,void();
        int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r),upd(p);
    }
    void Mdf(int p,ll v) {
        if(t[p].mx<=v)return;
        if(t[p].sec<v)return Md(p,v);
        down(p),Mdf(p<<1,v),Mdf(p<<1|1,v),upd(p);
    }
    ll qry(int p,int l,int r) {
        if(t[p].l>=l&&t[p].r<=r)return t[p].s;
        int mid=t[p].l+t[p].r>>1;ll s=0;down(p);
        if(l<=mid)s=qry(p<<1,l,r);
        if(r>mid)s+=qry(p<<1|1,l,r);
        return s;
    } 
    void solve() {
        build(1,1,n);
        for(int i=1;i<=m;i++) {
            int op=O[i];
            if(op==1)Mdf(1,V[i]);
            else cout<<qry(1,L[i],R[i])<<'\n';
        }
    }
}
bool ED;
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cerr<<"Memory: "<<(&ST-&ED)/1024.0/1024.0<<" MB\n";
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    bool A=1;
    for(int i=1;i<=m;i++) {
        cin>>O[i];
        if(O[i]==1)cin>>V[i];
        if(O[i]==2)A=0;
        if(O[i]==3)cin>>L[i]>>R[i];
    }
    if(A)sub::solve(),exit(0);
    build(1,1,n);
    for(int i=1;i<=m;i++) {
        int op=O[i];
        if(op==1)Mdf(1,V[i]);
        else if(op==2)Add(1);
        else cout<<qry(1,L[i],R[i])<<'\n';
    }
    return 0;
}