#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1000001;
int n,m,a[N],b[N],c[N];
vector<int> e[N];
vector<pair<int,int>> d[N];
struct sgt
{
    struct tree
    {
        int l,r;
        ll s,w,k1,k2,t0,t1,t2;
    }T[N<<2];
    void pushup(int x)
    {
        T[x].s=T[x<<1].s+T[x<<1|1].s;
        T[x].w=max(T[x<<1].w,T[x<<1|1].w);
        T[x].t0=max(T[x<<1].t0,T[x<<1|1].t0);
        T[x].t1=T[x<<1].t1+T[x<<1|1].t1;
        T[x].t2=T[x<<1].t2+T[x<<1|1].t2;
    }
    void maketag1(int x,ll k)
    {
        T[x].s+=T[x].t1*k;
        T[x].w+=T[x].t0*k;
        T[x].k1+=k;
    }
    void maketag2(int x,ll k)
    {
        T[x].s=T[x].t2*k;
        T[x].w=k;
        T[x].k1=0;
        T[x].k2=k;
    }
    void pushdown(int x)
    {
        if(T[x].k2)
        {
            maketag2(x<<1,T[x].k2);
            maketag2(x<<1|1,T[x].k2);
            T[x].k2=0;
        }
        if(T[x].k1)
        {
            maketag1(x<<1,T[x].k1);
            maketag1(x<<1|1,T[x].k1);
            T[x].k1=0;
        }
    }
    void build(int x,int l,int r)
    {
        T[x].l=l,T[x].r=r;
        if(l==r) return;
        int z=l+r>>1;
        build(x<<1,l,z);
        build(x<<1|1,z+1,r);
        pushup(x);
    }
    void add1(int x,int q,ll k,ll t1,ll t2)
    {
        if(T[x].l==T[x].r)
        {
            T[x].s=T[x].w=k;
            T[x].t0=T[x].t1=t1;
            T[x].t2=t2;
            return;
        }
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        if(q<=z) add1(x<<1,q,k,t1,t2);
        else add1(x<<1|1,q,k,t1,t2);
        pushup(x);
    }
    void add2(int x,int l,int r,ll k)
    {
        if(T[x].l>=l&&T[x].r<=r)
        {
            maketag2(x,k);
            return;
        }
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        if(l<=z) add2(x<<1,l,r,k);
        if(r>z) add2(x<<1|1,l,r,k);
        pushup(x);
    }
    int find(int x,ll k)
    {
        if(T[x].l==T[x].r) return T[x].l;
        pushdown(x);
        if(T[x<<1].w>=k) return find(x<<1,k);
        else return find(x<<1|1,k);
    }
    ll sum(int x,int l,int r)
    {
        if(T[x].l>=l&&T[x].r<=r) return T[x].s;
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        ll s=0;
        if(l<=z) s+=sum(x<<1,l,r);
        if(r>z) s+=sum(x<<1|1,l,r);
        return s;
    }
}T1,T2;
void solve(vector<int> &p,int l,int r)
{
    if(l==r)
    {
        // printf("%d: ",l);
        // for(auto i:p) printf("%d ",i);printf("\n");
        for(auto i:p) e[l].push_back(i);
        return;
    }
    int z=l+r>>1;
    static int S[N],T;
    T=0;
    for(int i=l;i<=z;++i)
    {
        while(T>0&&b[S[T-1]]==b[i]&&c[S[T]]>c[i]) --T;
        while(T>1&&(ll)(c[i]-c[S[T]])*(b[i]-b[S[T-1]])<(ll)(c[i]-c[S[T-1]])*(b[i]-b[S[T]])) --T;
        S[++T]=i;
    }
    vector<int> p1,p2;
    // printf("%d %d:\n",l,r);
    int x=1;
    // for(int i=1;i<=T;++i) printf("%d ",S[i]);printf("\n");
    for(auto i:p)
    {
        while(x+1<=T&&(c[S[x+1]]-c[S[x]])<=(ll)i*(b[S[x+1]]-b[S[x]])) ++x;
        // printf("%d %d\n",x,S[x]);
        // printf("%lld %d\n",c[S[x]]-(ll)i*b[S[x]],a[i]);
        if(c[S[x]]-(ll)i*b[S[x]]<=a[i]) p1.push_back(i);
        else p2.push_back(i);
    }
    solve(p1,l,z);
    solve(p2,z+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;++i)
    {
        int z;
        scanf("%d",&z);
        if(z==1)
        {
            b[i]+=b[i-1];
            scanf("%d",&c[i]);
        }
        else if(z==2)
        {
            ++b[i];
            --m,--i;
            d[i].push_back(make_pair(0,0));
        }
        else if(z==3)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            --m,--i;
            d[i].push_back(make_pair(l,r));
        }
    }
    vector<int> p;
    for(int i=1;i<=n;++i) p.push_back(i);
    solve(p,1,m+1);
    T1.build(1,1,n);
    T2.build(1,1,n);
    for(int i=1;i<=n;++i)
    {
        T1.add1(1,i,a[i],i,1);
    }
    for(int i=0;i<=m;++i)
    {
        if(T2.T[1].w>=c[i])
        {
            T2.add2(1,T2.find(1,c[i]),n,c[i]);
        }
        for(auto j:e[i])
        {
            T1.add1(1,j,0,0,0);
            T2.add1(1,j,c[i],j,1);
        }
        for(auto j:d[i])
        {
            if(j.first==0)
            {
                T1.maketag1(1,1);
                T2.maketag1(1,1);
            }
            else
            {
                printf("%lld\n",T1.sum(1,j.first,j.second)+T2.sum(1,j.first,j.second));
            }
        }
    }
    return 0;
}