#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back
#define int long long

using namespace std;

typedef long long ll;
typedef pair < ll, ll > pt;

const int N = 2e5 + 500;
const int OFF = (1 << 18);

ll ccw(pt A, pt B, pt C) {
    return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}

struct node{
    int fir, lst, brj;
    ll sum_ind, sum_val;
    ll max_val, min_val;
    node(){
        fir = -1; lst = -1; brj = 0;
        sum_ind = 0; sum_val = 0;
        max_val = 0; min_val= 0 ;
    }
};

node mrg(node A, node B) {
    if(A.brj == 0) return B;
    if(B.brj == 0) return A;
    node C;
    C.fir = A.fir; C.min_val = A.min_val;
    C.lst = B.lst; C.max_val = B.max_val;
    C.brj = A.brj + B.brj;
    C.sum_ind = A.sum_ind + B.sum_ind;
    C.sum_val = A.sum_val + B.sum_val;
    return C;
}

int prop_ind[2 * OFF];
ll prop_set[2 * OFF];
node T[2 * OFF];

void refresh(int x) {
    if(T[x].brj == 0) {
    	prop_set[x] = -1; prop_ind[x] = 0; return;
    }
    if(prop_set[x] != -1) {
        T[x].min_val = prop_set[x]; T[x].max_val = prop_set[x];
        T[x].sum_val = prop_set[x] * T[x].brj;
        if(x < OFF) {
            prop_ind[2 * x] = 0; prop_ind[2 * x + 1] = 0;
            prop_set[2 * x] = prop_set[x];
            prop_set[2 * x + 1] = prop_set[x];
        }
        prop_set[x] = -1;
    }
    if(prop_ind[x]) {
        T[x].min_val += (ll)T[x].fir * prop_ind[x];
        T[x].max_val += (ll)T[x].lst * prop_ind[x];
        T[x].sum_val += (ll)T[x].sum_ind * prop_ind[x];
        if(x < OFF) {
            prop_ind[2 * x] += prop_ind[x];
            prop_ind[2 * x + 1] += prop_ind[x];
        }
        prop_ind[x] = 0;
    }
}

void set_val(int i, int a, int b, ll v) {
    refresh(i);
    if(T[i].min_val > v) {
        prop_ind[i] = 0; prop_set[i] = v;
        refresh(i); return;
    }
    if(T[i].fir == -1 || T[i].max_val <= v) return;
    set_val(2 * i, a, (a + b) / 2, v);
    set_val(2 * i + 1, (a + b) / 2 + 1, b, v);
    T[i] = mrg(T[2 * i], T[2 * i + 1]);
}

ll query(int i, int a, int b, int lo, int hi) {
    refresh(i);
    if(lo <= a && b <= hi) return T[i].sum_val;
    if(a > hi || b < lo) return 0;
    return query(2 * i, a, (a + b) / 2, lo, hi) + query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}

void ubaci(int i, int a, int b, int gdje, ll sto) {
    refresh(i);
    if(a == b) {
        T[i].fir = a; T[i].lst = a; T[i].brj = 1;
        T[i].sum_ind = a; T[i].sum_val = sto;
        T[i].max_val = sto; T[i].min_val = sto;
        return;
    }
    if(gdje <= (a + b) / 2)
        ubaci(2 * i, a, (a + b) / 2, gdje, sto), refresh(2 * i + 1);
    else
        ubaci(2 * i + 1, (a + b) / 2 + 1, b, gdje, sto), refresh(2 * i);
    T[i] = mrg(T[2 * i], T[2 * i + 1]);
}

ll ob_T[2 * OFF], ind_T[2 * OFF];
ll vrijeme = 0;

void ob_delete(int i) {
    ob_T[OFF + i] = 0; ind_T[OFF + i] = 0;
    for(i = (i + OFF) / 2; i ; i /= 2) {
        ob_T[i] = ob_T[2 * i] + ob_T[2 * i + 1];
        ind_T[i] = ind_T[2 * i] + ind_T[2 * i + 1];
    }
}

ll query2(int i, int a, int b, int lo, int hi) {
    if(lo <= a && b <= hi) return ob_T[i] + ind_T[i] * vrijeme;
    if(a > hi || b < lo) return 0;
    return query2(2 * i, a, (a + b) / 2, lo, hi) + query2(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}

struct convex_hull {
    vector < pt > v;

    void ubaci(pt A) {

        if(!v.empty() && A.X == v.back().X) {
            if(A.Y >= v.back().Y)
                return;
            else {
                v.pop_back();
            }
        }

        while((int)v.size() >= 2 && ccw(v[(int)v.size() - 2], v[(int)v.size() - 1], A) <= 0) {
            v.pop_back();
        }

        v.PB(A);
    }

    ll query(ll x) {
    	if(v.empty()) return (ll)1e18;
        ll ans = v[0].X * x + v[0].Y;
        int lo = 0, hi = (int)v.size() - 1;
        while(lo < hi) {
            int mid = (lo + hi) / 2;
            ll v1 = v[mid].X * x + v[mid].Y;
            ll v2 = v[mid + 1].X * x +v[mid + 1].Y;
            if(v1 < v2) ans = min(ans, v1), hi = mid;
            else ans = min(ans, v2), lo = mid + 1;
        }
        return ans;
    }
};

int n, q, kad[N], lo[N], hi[N], mid[N];
vector< int > immi[N];
ll A[N];
int q_ty[N];
ll q_val[N];
int q_l[N], q_r[N];
vector < int > izb[N];

signed main(){
    memset(prop_set, -1, sizeof(prop_set));
    scanf("%lld%lld", &n, &q);
    for(int i = 1;i <= n;i++) {
        scanf("%lld", A + i);
        ob_T[OFF + i] = A[i]; ind_T[OFF + i] = i;
    }
    for(int i = OFF - 1; i ; i--)
        ob_T[i] = ob_T[2 * i] + ob_T[2 * i + 1], ind_T[i] = ind_T[2 * i] + ind_T[2 * i + 1];

    for(int i = 0;i < q;i++) {
        scanf("%lld", q_ty + i);
        if(q_ty[i] == 1) {
            scanf("%lld", q_val + i);
        } else if(q_ty[i] == 3) {
            scanf("%lld%lld", q_l + i, q_r + i);
        }
    }

    for (int i=1;i<=n;++i) lo[i]=0,hi[i] = q - 1;
    convex_hull conv;
    for (int z=0;z<18;++z)
    {
        conv.v.clear();
        for (int i=0;i<q;++i) immi[i].clear();
        for (int i=1;i<=n;++i)
        {
            mid[i]=(lo[i]+hi[i])/2;
            immi[mid[i]].push_back(i);
        }
        int ci=0;
        for (int i=0;i<q;++i)
        {
            if (q_ty[i]==2) ++ci;
            if (q_ty[i]==1) conv.ubaci({-ci,q_val[i]});
            for (auto x: immi[i])
            {
                ll re=conv.query(x),z=A[x];
                if (re<z) hi[x]=mid[x];
                else lo[x]=mid[x]+1;
            }
        }
    }

    for(int i = 1;i <= n;i++) {
        //printf("i %lld : %lld\n", i, mid[i]);
        //int x; scanf("%lld", &x);
        izb[mid[i]].PB(i);
    }

    // DODIN PRECOMPUTE

    for(int i = 0;i < q;i++) {
        if(q_ty[i] == 3) {
            printf("%lld\n", query(1, 0, OFF - 1, q_l[i], q_r[i]) + query2(1, 0, OFF - 1, q_l[i], q_r[i]));
        } else if(q_ty[i] == 2) {
            vrijeme++; prop_ind[1]++;
        } else {
            set_val(1, 0, OFF - 1, q_val[i]);
            for(int x : izb[i]) {
                ubaci(1, 0, OFF - 1, x, q_val[i]);
                ob_delete(x);
            }
        }
        //printf("%lld %lld\n", T[1].fir, T[1].lst);
        //printf("%lld %lld\n", T[1].min_val, T[1].max_val);
        //printf("%lld\n", T[1].brj);
    }

    return 0;
}