#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 500500
#define int long long
#define ll __int128
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

void write(reg ll x)
{
    if(x>9)write(x/10);
    putchar('0'+x%10);
}

int n,q,a[N],b[N];

IL void cmax(reg int &x,reg int y){x<y?x=y:0;}
IL int max(reg int x,reg int y){return x>y?x:y;}
IL int min(reg int x,reg int y){return x<y?x:y;}

#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)

int l[N<<2],r[N<<2],mx[N<<2],rsum[N<<2],tag1[N<<2],tag2[N<<2];
ll sumb[N<<2];

int dfs(reg int o,reg int k)
{
    if(l[o]==r[o])return max(mx[o],k);
    if(mx[ls]>k)return dfs(ls,k)+rsum[o];
    return dfs(rs,k)+k*(r[ls]-l[ls]+1);
}

IL void pushupa(reg int o)
{
    mx[o]=max(mx[ls],mx[rs]);
    rsum[o]=dfs(rs,mx[ls]);
}

IL void pushupb(reg int o)
{
    sumb[o]=sumb[ls]+sumb[rs];
    sumb[o]+=(ll)tag1[o]*(r[o]-l[o]+1)+(ll)tag2[o]*rsum[o];
}

void apply(reg int o,reg int k,reg int t)
{
    if(l[o]==r[o])
    {
        sumb[o]+=max(k,mx[o])*t;
        return;
    }
    if(k>=mx[ls])tag1[ls]+=k*t,sumb[ls]+=(ll)k*t*(r[ls]-l[ls]+1),apply(rs,k,t);
    else tag2[o]+=t,apply(ls,k,t);
    pushupb(o);
}

void pushdown(reg int o)
{
    if(tag2[o])apply(rs,mx[ls],tag2[o]),tag2[o]=0;
}

void build(reg int o,reg int L,reg int R)
{
    l[o]=L,r[o]=R;
    if(L==R)mx[o]=a[L];
    else build(ls,L,mid),build(rs,mid+1,R),pushupa(o);
}

void change(reg int o,reg int p,reg int k)
{
    if(l[o]==r[o])mx[o]=k;
    else pushdown(o),change(mid>=p?ls:rs,p,k),pushupa(o);
}

void modify(reg int o,reg int L,reg int R,reg int &k)
{
    if(L<=l[o]&&r[o]<=R)return apply(o,k,1),cmax(k,mx[o]);
    if(L>r[o]||l[o]>R)return;
    modify(ls,L,R,k),modify(rs,L,R,k),pushupb(o);
}

ll query(reg int o,reg int L,reg int R)
{
    if(L<=l[o]&&r[o]<=R)return sumb[o];
    if(L>r[o]||l[o]>R)return 0;
    pushdown(o);
    return query(ls,L,R)+query(rs,L,R)+(ll)tag1[o]*(min(R,r[o])-max(L,l[o])+1);
}

#undef ls
#undef rs
#undef mid

main()
{
    n=read(),q=read();
    for(reg int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    for(reg int op,l,r,k;q--;)
    {
        op=read(),l=read(),r=read();
        if(op==1)change(1,l,r);
        else if(op==2)k=0,modify(1,l,r,k);
        else write(query(1,l,r)),puts("");
    }
}