#include<bits/stdc++.h>
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll; 
typedef __int128 i128;
typedef array<ll,2> pr; 
typedef vector<int> vec;
const int MAXN = 2e5+10;

int n,q; ll a[MAXN];
int o[MAXN]; ll x[MAXN],y[MAXN];
pr arr[MAXN]; int rk[MAXN],num;
vec mdf[MAXN];
 
namespace T{ //求出每个位置从何时开始被影响到
    int t[MAXN],st[MAXN],top;

    ll X(int id){return arr[id][0];}
    ll Y(int id){return arr[id][1];}

    void solve(vec o,int l,int r){
        if(o.empty() || l>r)return;
        vec vL,vR;
        top = 0;
        for(int i=l;i<=mid;i++){
            int z = i;
            if(top){
                int y = st[top];
                if(X(y) == X(z)){
                    if(Y(y) > Y(z))top--;
                    else continue;
                }
            }
            while(top>=2){
                int x = st[top-1],y = st[top];
                if((i128)(Y(y)-Y(x))*(X(z)-X(y)) >= (i128)(Y(z)-Y(y))*(X(y)-X(x)))top--;
                else break;
            }
            st[++top] = z;
        }
        for(auto id : o){
            ll k = id,b = a[id];
            while(top>=2){
                int x = st[top-1],y = st[top];
                if((i128)(Y(y)-Y(x)) >= (i128)(X(y)-X(x)) * k)top--;
                else break;
            }
            int j = st[top];
            int flag = k * X(j) + b - Y(j) > 0;
            if(flag)t[id] = mid,vL.push_back(id);
            else vR.push_back(id);
        }
        solve(vL,l,mid-1); solve(vR,mid+1,r);
    }
    void solve(){
        for(int i=1,cnt=0;i<=q;i++){                                
            if(o[i] == 2)cnt++;
            else if(o[i] == 1)arr[++num] = (pr){cnt,x[i]},rk[num] = i;
        }
        vec o; for(int i=n;i>=1;i--)o.push_back(i),t[i] = q+1;
        solve(o,1,num);
        for(int i=1;i<=n;i++)if(t[i] != q+1)mdf[rk[t[i]]].push_back(i);
    }
}

struct Seg{
    ll sum[MAXN<<2],w[MAXN<<2],rv[MAXN<<2],cv[MAXN<<2];
    int tag[MAXN<<2],cnt[MAXN<<2],rw[MAXN<<2];
    void pu(int x){
        sum[x] = sum[lc(x)] + sum[rc(x)];
        w[x] = w[lc(x)] + w[rc(x)];
        cnt[x] = cnt[lc(x)] + cnt[rc(x)];
        rv[x] = cnt[rc(x)] ? rv[rc(x)] : rv[lc(x)];
        rw[x] = cnt[rc(x)] ? rw[rc(x)] : rw[lc(x)];
    }
    void cover(int x,ll v){
        sum[x] = cnt[x] * v; rv[x] = v; tag[x] = 0; cv[x] = v;
    }
    void add(int x,int v){
        sum[x] += w[x] * v; rv[x] += rw[x] * v; tag[x] += v; 
    }
    void pd(int x){
        if(cv[x] != -1)cover(lc(x),cv[x]),cover(rc(x),cv[x]),cv[x] = -1;
        if(tag[x])add(lc(x),tag[x]),add(rc(x),tag[x]),tag[x] = 0;
    }
    //
    void build(int x,int l,int r,int t){
        cv[x] = -1; 
        if(l==r){
            if(t)sum[x] = a[l],w[x] = l;
            return;
        }
        build(lc(x),l,mid,t); build(rc(x),mid+1,r,t);
        pu(x);
    }
    void flip(int x,int l,int r,int pos,ll p,int q){
        if(l==r){
            sum[x] = rv[x] = p; w[x] = rw[x] = q; cnt[x] = (q>0);
            return;
        }
        pd(x);
        (pos<=mid) ? flip(lc(x),l,mid,pos,p,q) : flip(rc(x),mid+1,r,pos,p,q);
        pu(x);
    }
    ll qry(int x,int l,int r,int ql,int qr){
        if(ql>qr)return 0; if(ql<=l && qr>=r)return sum[x];
        pd(x); 
        ll ret = 0;
        if(ql<=mid)ret += qry(lc(x),l,mid,ql,qr);
        if(qr>mid)ret += qry(rc(x),mid+1,r,ql,qr);
        return ret;
    }
    void mdf(int x,int l,int r,int ql,int qr,ll v){
        if(ql>qr)return; if(ql<=l && qr>=r)return cover(x,v);
        pd(x);
        if(ql<=mid)mdf(lc(x),l,mid,ql,qr,v);
        if(qr>mid)mdf(rc(x),mid+1,r,ql,qr,v);
        pu(x);
    }
    int find(int x,int l,int r,ll v){
        if(!cnt[x] || rv[x] <= v)return n+1;
        if(l==r)return r;
        pd(x);
        int ans = find(lc(x),l,mid,v); if(ans != n+1)return ans;
        return find(rc(x),mid+1,r,v);
    }
}va,vb;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++){
        cin>>o[i];
        if(o[i] == 1){
            cin>>x[i];
        }else if(o[i] == 3){
            cin>>x[i]>>y[i];
        }
    }
    T::solve();
    va.build(1,1,n,0); vb.build(1,1,n,1);
    for(int i=1;i<=q;i++){
        if(o[i] == 1){
            int j = va.find(1,1,n,x[i]);
            va.mdf(1,1,n,j,n,x[i]);

            for(auto j : mdf[i]){
                vb.flip(1,1,n,j,0,0);
                va.flip(1,1,n,j,x[i],j);
            }
        }else if(o[i] == 2){
            va.add(1,1); vb.add(1,1);
        }else{
            ll sum = va.qry(1,1,n,x[i],y[i]) + vb.qry(1,1,n,x[i],y[i]);
            cout<<sum<<"\n";
        }
    }

    return 0;
}