//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

//const int max_n = -1, inf = 1000111222;


const ld inf = 1e18;
struct line {

    ll m, b; ld x;
    ll val; bool isQuery;
    line(ll _m = 0, ll _b = 0) :
        m(_m), b(_b), val(0), x(-inf), isQuery(false) {}

    ll eval(ll x) const { return m * x + b;    }
    bool parallel(const line &l) const { return m == l.m; }
    ld intersect(const line &l) const {
        return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
    }
    bool operator < (const line &l) const {
        if(l.isQuery) return x < l.val;
        else return m < l.m;
    }
};
struct convex_hull_trick {
/// max
    set<line> hull;
    typedef set<line> :: iterator iter;

    bool cPrev(iter it) { return it != hull.begin(); }
    bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

    bool bad(const line &l1, const line &l2, const line &l3) {
        return l1.intersect(l3) <= l1.intersect(l2);
    }
    bool bad(iter it) {
        return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
    }

    iter update(iter it) {
        if(!cPrev(it)) return it;
        ld x = it -> intersect(*prev(it));
        line tmp(*it); tmp.x = x;
        it = hull.erase(it);
        return hull.insert(it, tmp);
    }

    void addLine(ll m, ll b) {
        m *= -1;
        b *= -1;
        line l(m, b);
        iter it = hull.lower_bound(l);
        if(it != hull.end() && l.parallel(*it)) {
            if(it -> b < b) it = hull.erase(it);
            else return;
        }

        it = hull.insert(it, l);
        if(bad(it)) return (void) hull.erase(it);

        while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
        while(cNext(it) && bad(next(it))) hull.erase(next(it));

        it = update(it);
        if(cPrev(it)) update(prev(it));
        if(cNext(it)) update(next(it));
    }

    ll query(ll x) const {
        if(hull.empty()) return -inf;
        line q; q.val = x, q.isQuery = 1;
        iter it = --hull.lower_bound(q);
        return -it -> eval(x);
    }
};


template <class T>
struct fenwick {
public:
    int n;
    vector <T> t; /// !!!


    fenwick (int n) : n(n) {
        t.assign(n, T(0));
    }

    inline void upd (int i, T x) {
        for (; i < n; i = i | (i + 1)) t[i] += x;
    }

    inline T sum (int r) {
        T ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) ans += t[r];
        return ans;
    }

    inline T sum (int l, int r) {
        if (l > r) return T(0); /// !!!
        return sum(r) - sum(l - 1);
    }
};

const ll linf = inf * 1ll * inf;

struct node {

    ll ans, push, k, b, cnt, m, sum_b, sum_k;

    /// not existing node
    node () : ans(0), push(-linf), cnt(0), k(0), b(0), m(0), sum_b(0), sum_k(0)  {}

    node (ll x, int id, int m) : ans(x), k(id), b(x - m * 1ll * id), push(-linf), m(m), cnt(1), sum_k(id), sum_b(x - m * 1ll * id)  {
        /// set to not existing node if needed

    }

    inline ll val (ll x) const {
        if (k == 0) {
            return -linf;
        }
        return k * x + b;
    }
};



inline node pull (node a, node b) {
    node res;
    res.ans = a.ans + b.ans;
    res.cnt = a.cnt + b.cnt;
    res.sum_b = a.sum_b + b.sum_b;
    res.sum_k = a.sum_k + b.sum_k;
    if (b.k) {
        res.k = b.k;
        res.b = b.b;
    }
    else {
        res.k = a.k;
        res.b = a.b;
    }
    return res;
}

struct segment_tree {
    vector <node> t;
    int n;

    segment_tree () {}

    inline void build (int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = node(); /// think
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        t[v] = pull(t[v << 1], t[v << 1 | 1]);
    }

    segment_tree (int n) : n(n) {
        t.resize(4 * n);
        build(1, 0, n - 1);
    }

    inline void push (int v, int tl, int tr) {
        if (tl != tr && t[v].push != -linf) {
            t[v << 1].ans = t[v].push * t[v << 1].cnt;
            t[v << 1 | 1].ans = t[v].push * t[v << 1 | 1].cnt;

            t[v << 1].sum_b = t[v].push * t[v << 1].cnt - t[v << 1].sum_k * t[v].m;
            t[v << 1 | 1].sum_b = t[v].push * t[v << 1 | 1].cnt - t[v << 1 | 1].sum_k * t[v].m;

            t[v << 1].b = t[v].push - t[v].m * t[v << 1].k;
            t[v << 1 | 1].b = t[v].push - t[v].m * t[v << 1 | 1].k;

            t[v << 1].push = t[v].push;
            t[v << 1 | 1].push = t[v].push;

            t[v << 1].m = t[v].m;
            t[v << 1 | 1].m = t[v].m;

            t[v].push = -linf;
        }
    }

    inline void update (int v, int tl, int tr, int l, int r, int x) { /// think
        push(v, tl, tr);
        if (l > r) return;
        if (tl == l && tr == r) { /// think
            // t[v]
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;
        update(v << 1, tl, tm, l, min(r, tm), x);
        update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, x);
        t[v] = pull(t[v << 1], t[v << 1 | 1]);
    }

    inline void update1 (int v, int tl, int tr, int pos, ll x, int cur_k) { /// think
        push(v, tl, tr);
        if (tl == tr) {
            t[v] = node(x, tr + 1, cur_k);
            return;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            update1(v << 1, tl, tm, pos, x, cur_k);
        }
        else {
            update1(v << 1 | 1, tm + 1, tr, pos, x, cur_k);
        }
        t[v] = pull(t[v << 1], t[v << 1 | 1]);
    }

    inline node query (int v, int tl, int tr, int l, int r) {
        push(v, tl, tr);
        if (l > r) return node();
        if (tl == l && tr == r) {
            return t[v];
        }
        int tm = (tl + tr) >> 1;
        return pull(query(v << 1, tl, tm, l, min(r, tm)), query(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r));
    }

    inline void upd (int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    inline void upd1 (int pos, ll x, int cur_k) {
        update1(1, 0, n - 1, pos, x, cur_k);
    }

    inline node get (int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    inline void make_push (int v, int tl, int tr, ll val, int m) {
        t[v].ans = t[v].cnt * val;
        t[v].b = val - t[v].k * m;
        t[v].sum_b = val * t[v].cnt - t[v].sum_k * m;
        t[v].push = val;
        t[v].m = m;
        push(v, tl, tr);
    }

    inline void go (int v, int tl, int tr, ll val, int m) {
        push(v, tl, tr);
        if (!t[v].k) {
            return;
        }
        if (tl == tr) {
            if (t[v].val(m) > val) {
                make_push(v, tl, tr, val, m);
            }
            return;
        }
        int tm = (tl + tr) >> 1;
        push(v << 1, tl, tm);
        push(v << 1 | 1, tm + 1, tr);
        if (t[v << 1].val(m) > val) {
            make_push(v << 1 | 1, tm + 1, tr, val, m);
            go(v << 1, tl, tm, val, m);
        }
        else {
            go(v << 1 | 1, tm + 1, tr, val, m);
        }
        t[v] = pull(t[v << 1], t[v << 1 | 1]);
    }
};

inline ll sum (ll a0, ll n) {
    return ((2 * a0 + n - 1) * n) / 2ll;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, q;
    cin >> n >> q;
    vector <ll> a(n);
    for (auto &i : a) cin >> i;
    vector <int> cnt(n), t(n), l(n), r(n);
    for (int i = 0; i < q; i++) {
        cin >> t[i];
        if (i) {
            cnt[i] = cnt[i - 1];
        }
        if (t[i] == 1) {
            cin >> r[i];
        }
        else if (t[i] == 3) {
            cin >> l[i] >> r[i];
            --l[i], --r[i];
        }
        else {
            ++cnt[i];
        }
    }
    vector <int> L(n, 0), R(n, q);
    while (true) {
        bool ok = false;
        vector <vector <int> > have(q + 1);
        for (int i = 0; i < n; i++) {
            if (L[i] != R[i]) {
                int mid = (L[i] + R[i]) >> 1;
                have[mid].pb(i);
                ok = true;
            }
        }
        if (!ok) {
            break;
        }
        convex_hull_trick cht;
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                cht.addLine(-cnt[i], r[i]);
            }
            for (int id : have[i]) {
                if (!cht.hull.empty() && cht.query(id + 1) <= a[id]) {
                    R[id] = i;
                }
                else {
                    L[id] = i + 1;
                }
            }
        }
    }
    vector <vector <int> > have(q);
    fenwick <ll> T(n);
    for (int i = 0; i < n; i++) {
        if (R[i] < q) {
            have[R[i]].pb(i);
        }
        T.upd(i, a[i]);
    }
    segment_tree tr(n);
    for (int i = 0; i < q; i++) {
        if (t[i] == 1) {
            for (int id : have[i]) {
                tr.upd1(id, r[i], cnt[i]);
                T.upd(id, -a[id]);
            }
            tr.go(1, 0, n - 1, r[i], cnt[i]);
        }
        else if (t[i] == 2) {

        }
        else {
            node res = tr.get(l[i], r[i]);
            ll ans = T.sum(l[i], r[i]) + cnt[i] * sum(l[i] + 1, r[i] - l[i] + 1) + res.sum_b;
            cout << ans << '\n';
        }
    }
}