#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 200500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

int n, q;
const int maxN = 2e5 + 10;
ll a[maxN];
int tp[maxN];
int l[maxN], r[maxN];
ll v[maxN];
ll b[maxN], c[maxN];
int frst[maxN];

vector<int> g_frst[N];

namespace PRE_SEG {
    int cnt;
    ll t1[N << 2], t2[N << 2];

    void build(int v, int tl, int tr) {
        if (tl == tr) {
            t1[v] = a[tl];
            t2[v] = tl;
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        t1[v] = t1[v << 1] + t1[v << 1 | 1];
        t2[v] = t2[v << 1] + t2[v << 1 | 1];
    }

    void upd(int v, int tl, int tr, int p) {
        if (tl == tr) {
            t1[v] = t2[v] = 0;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (p <= tm)
            upd(v << 1, tl, tm, p);
        else
            upd(v << 1 | 1, tm + 1, tr, p);
        t1[v] = t1[v << 1] + t1[v << 1 | 1];
        t2[v] = t2[v << 1] + t2[v << 1 | 1];
    }

    pll get(int v, int tl, int tr, int l, int r) {
        if (r < tl || tr < l || l > r)
            return {0, 0};
        if (l <= tl && tr <= r)
            return {t1[v], t2[v]};
        int tm = (tl + tr) >> 1;
        pll a = get(v << 1, tl, tm, l, r);
        pll b = get(v << 1 | 1, tm + 1, tr, l, r);
        return {a.f + b.f, a.s + b.s};
    }

    ll get(int l, int r) {
        pll res = get(1, 1, n, l, r);
        return res.f + res.s * cnt;
    }
};
namespace AFTER_SEG {
    ll cnt[N << 2];
    ll t1[N << 2], tc[N << 2];
    ll t2[N << 2];
    ll mx1[N << 2], mx2[N << 2];
    ll mn1[N << 2], mn2[N << 2];

    ll lazy[N << 2];

    void build(int v, int tl, int tr) {
        cnt[v] = 0;
        tc[v] = 0;

        t1[v] = t2[v] = 0;
        mx1[v] = mx2[v] = 0;
        mn1[v] = mn2[v] = 0;
        lazy[v] = -1;

        if (tl == tr)
            return;
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
    }

    void pull(int v) {
        cnt[v] = 0;
        tc[v] = 0;
        t1[v] = t2[v] = 0;
        mn1[v] = mn2[v] = INF;
        mx1[v] = mx2[v] = -INF;
        lazy[v] = -1;
        for (auto u: {v << 1, v << 1 | 1}) {
            if (cnt[u] == 0)
                continue;
            cnt[v] += cnt[u];
            t1[v] += t1[u];
            t2[v] += t2[u];
            mn1[v] = min(mn1[v], mn1[u]);
            mn2[v] = min(mn2[v], mn2[u]);
            mx1[v] = max(mx1[v], mx1[u]);
            mx2[v] = max(mx2[v], mx2[u]);
        }
    }

    void push(int v) {
        if (lazy[v] != -1) {
            for (auto u: {v << 1, v << 1 | 1}) {
                if (cnt[u] == 0)
                    continue;
                lazy[u] = lazy[v];
                tc[u] = 0;
                t1[u] = cnt[u] * lazy[u];
                mn1[u] = lazy[u];
                mx1[u] = lazy[u];
            }
            lazy[v] = -1;
        }
        if (tc[v] != 0) {
            for (auto u: {v << 1, v << 1 | 1}) {
                if (cnt[u] == 0)
                    continue;
                tc[u] += tc[v];
                t1[u] += t2[u] * tc[v];
                mn1[u] += mn2[u] * tc[v];
                mx1[u] += mx2[u] * tc[v];
            }
            tc[v] = 0;
        }
    }

    void add(int v, int tl, int tr, int p, ll x) {
        if (tl == tr) {
            cnt[v] = 1;
            tc[v] = 0;
            t1[v] = mn1[v] = mx1[v] = x;
            t2[v] = mn2[v] = mx2[v] = p;
            lazy[v] = -1;
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        if (p <= tm)
            add(v << 1, tl, tm, p, x);
        else
            add(v << 1 | 1, tm + 1, tr, p, x);
        pull(v);
    }

    void upd(int v, int tl, int tr, ll x) {
        if (cnt[v] == 0)
            return;
        if (mx1[v] <= x)
            return;
        if (mn1[v] >= x) {
            lazy[v] = x;
            tc[v] = 0;
            mn1[v] = mx1[v] = x;
            t1[v] = cnt[v] * x;
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        upd(v << 1, tl, tm, x);
        upd(v << 1 | 1, tm + 1, tr, x);
        pull(v);
    }

    ll get(int v, int tl, int tr, int l, int r) {
        if (r < tl || tr < l || l > r)
            return 0;
        if (l <= tl && tr <= r)
            return t1[v];
        push(v);
        int tm = (tl + tr) >> 1;
        return get(v << 1, tl, tm, l, r) + get(v << 1 | 1, tm + 1, tr, l, r);
    }

    void upd() {
        if (cnt[1] == 0)
            return;
        tc[1]++;
        t1[1] += t2[1];
        mn1[1] += mn2[1];
        mx1[1] += mx2[1];
    }
};

void calc(int l, int r, vector<int> &INDS) {
    if (INDS.empty() || l > r) return;
    if (l == r) {
        for (int u: INDS) {
            if (tp[l] == 1) {
                if (b[u] > v[l]) frst[u] = l;
                else frst[u] = q + 1;
            }
        }
        return;
    }
    vector<pair<ll, ll>> lines;
    int cnt = 0;
    int MID = (l + r) / 2;
    for (int i = MID; i >= l; i--) {
        if (tp[i] == 2) {
            cnt++;
        } else if (tp[i] == 1) {
            if (!lines.empty() && lines.back().first == cnt) {
                if (lines.back().second <= v[i]) continue;
                lines.pop_back();
            }
            if (!lines.empty()) {
                assert(lines.back().first < cnt);
            }
            while ((int) lines.size() >= 2 &&
                   (cnt - lines.back().first) * (lines[lines.size() - 1].second - lines[lines.size() - 2].second)
                   > (lines[lines.size() - 1].first - lines[lines.size() - 2].first) * (v[i] - lines.back().second)) {
                lines.pop_back();
            }
            lines.emplace_back(cnt, v[i]);
        }
    }
    auto get_mn = [&](ll pt) {
        if (lines.empty()) return (ll) 1e18;
        int l = -1;
        int r = lines.size() - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (lines[mid].first * pt + lines[mid].second > lines[mid + 1].first * pt + lines[mid + 1].second) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return lines[r].first * pt + lines[r].second;
    };
    vector<int> INDS_L, INDS_R;
    for (int x: INDS) {
        if (b[x] + (ll) cnt * x > get_mn(x)) {
            INDS_L.emplace_back(x);
        } else {
            b[x] += (ll) cnt * x;
            INDS_R.emplace_back(x);
        }
    }
    INDS.clear();
    calc(l, MID, INDS_L);
    calc(MID + 1, r, INDS_R);
}

int ans[maxN];
mt19937 rnd(228);

void solve() {
//    srand(time(0));
    cin >> n >> q;
//    n = rnd() % 1000 + 1;
//    q = rnd() % 1000 + 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
//        a[i] = rnd() % 1000 + 1;
//        a[i] = inf;
//        cout << a[i] << " ??? " << endl;
    }
    for (int i = 1; i <= q; i++) {
        cin >> tp[i];
//        tp[i] = rnd() % 3 + 1;
        if (tp[i] == 1) {
            cin >> v[i];
//            v[i] = rnd() % 1000 + 1;
//            v[i] = 100000;
        } else if (tp[i] == 2) {
        } else if (tp[i] == 3) {
            cin >> l[i] >> r[i];
//            l[i] = rnd() % n + 1;
//            r[i] = rnd() % n + 1;
//            if (l[i] > r[i])
//                swap(l[i], r[i]);
        }
    }
    vector<int> INDS(n);
    iota(INDS.begin(), INDS.end(), 1);
    for (int i = 1; i <= n; i++) {
        b[i] = a[i];
    }
    for (int i = 1; i <= n; i++) {
        frst[i] = q + 1;
    }
    calc(1, q, INDS);


//    for (int i = 1; i <= n; i++) {
//        int my = q + 1;
//        ll CUR = a[i];
//        cout << CUR << " ???? " << frst[i] << " " << v[1] << " " << tp[1] << endl;
//        for (int j = 1; j <= q; j++) {
//            if (tp[j] == 2) {
//                CUR += i;
//            } else if (tp[j] == 1) {
//                if (CUR > v[j]) {
//                    my = j;
//                    break;
//                }
//            }
//        }
//        assert(my == frst[i]);
//    }

    PRE_SEG::build(1, 1, n);
    AFTER_SEG::build(1, 1, n);

    for (int i = 1; i <= n; i++)
        b[i] = a[i];

    for (int i = 1; i <= n; i++)
        g_frst[frst[i]].pb(i);

    for (int i = 1; i <= q; i++) {
        if (tp[i] == 1) {
            for (auto j: g_frst[i]) {
                PRE_SEG::upd(1, 1, n, j);
                AFTER_SEG::add(1, 1, n, j, v[i]);
                c[j] = 1;
                b[j] = v[i];
            }
            AFTER_SEG::upd(1, 1, n, v[i]);
//            cerr << n * v[i] << " " << AFTER_SEG::t1[1] << endl;
//            for (int j = 1; j <= n; j++)
//                b[j] = min(b[j], v[i]);
        }
        if (tp[i] == 2) {
            PRE_SEG::cnt++;
            AFTER_SEG::upd();

//            for (int j = 1; j <= n; j++)
//                b[j] += j;
        }
        if (tp[i] == 3) {
            ll res = 0;
            res += PRE_SEG::get(l[i], r[i]);
            res += AFTER_SEG::get(1, 1, n, l[i], r[i]);
//            ll tup = 0;
//            for (int j = l[i]; j <= r[i]; j++)
//                tup += b[j];
//            assert(tup == res);
            cout << res << "\n";
        }
    }

}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}