#include<bits/stdc++.h>
using namespace std;
#define N 500005
typedef long long ll;
int n,m,a[N];
struct seg{
    int l,r;
    ll mx,sum,ans,t1,t2;
}s[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
ll query(int u,ll x){
    if(s[u].l==s[u].r)return max(x,s[u].mx);
    if(s[ls].mx>x)return query(ls,x)+s[u].sum-s[ls].sum;
    return x*(s[ls].r-s[ls].l+1)+query(rs,x);
}
void pushup(int u){
    s[u].mx=max(s[ls].mx,s[rs].mx);
    s[u].ans=s[ls].ans+s[rs].ans;
    s[u].sum=s[ls].sum+query(rs,s[ls].mx);
}
void put(int u,ll k){s[u].ans+=k*(s[u].r-s[u].l+1);s[u].t1+=k;}
void put(int u,ll t,ll k){
    if(s[u].l==s[u].r){s[u].ans+=max(s[u].mx,k)*t;return;}
    if(s[ls].mx>k){
        s[u].ans+=(query(ls,k)+s[u].sum-s[rs].sum)*t;
        put(ls,t,k);
        s[rs].t2+=t;
        s[rs].ans+=(s[u].sum-s[ls].sum)*t;
    }else{
        s[u].ans+=((s[ls].r-s[ls].l+1)*k+query(rs,k))*t;
        put(ls,k*t);
        put(rs,t,k);
    }
}
void pushdown(int u){
    put(ls,s[u].t1);put(rs,s[u].t1);
    if(s[u].t2){
        put(ls,s[u].t2,s[u^1].mx);
        put(rs,s[u].t2,max(s[ls].mx,s[u^1].mx));
    }
    s[u].t1=s[u].t2=0;
}
void build(int u,int l,int r){
    s[u].l=l;s[u].r=r;if(l==r){s[u].mx=s[u].sum=a[l];return;}
    int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);
}
ll qry(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].mx;
    pushdown(u);return max(qry(ls,l,r),qry(rs,l,r));
}
ll query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].ans;
    pushdown(u);return query(ls,l,r)+query(rs,l,r);
}
void update(int u,int x,ll k){
    if(s[u].l==s[u].r){s[u].mx=s[u].sum=k;return;}
    pushdown(u);x<=s[ls].r?update(ls,x,k):update(rs,x,k);pushup(u);
}
void update(int u,int l,int r,ll k){
    if(s[u].l>r||s[u].r<l)return;
    if(s[u].l>=l&&s[u].r<=r){put(u,1,k);return;}
    pushdown(u);update(ls,l,r,k);update(rs,l,r,max(k,qry(ls,l,r)));pushup(u);
}
int main(){
    int opt,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)update(1,x,y);
        else if(opt==2)update(1,x,y,0);
        else printf("%lld\n",query(1,x,y));
    }
    return 0;
}