// generated at caterpillow.github.io/byot

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// generated at caterpillow.github.io/byot

namespace Treap {

    struct Lazy {
        ll mn;
        ll add;
    
        void operator+=(const Lazy& oth) {
            mn = min(mn, oth.mn - add);
            add += oth.add;
        }
    };
    
    const Lazy lid = {1'000'000'000'000'000'000, 0};
    
    Lazy chmin_tag(ll x) { Lazy lazy = lid; lazy.mn = x; return lazy; }
    Lazy add_tag(ll x) { Lazy lazy = lid; lazy.add = x; return lazy; }
    
    // You can implement your own monoid here for custom operations.
    struct Value {
        ll sum;
        ll mx, mxcnt, mx2;
    
        static Value make(ll x, ll len = 1) {
            return {x * len, x, len, -1'000'000'000'000'000'000};
        }
    
        bool can_break(const Lazy& lazy) {
            return lazy.mn >= mx && lazy.add == 0;
        }
    
        bool can_tag(const Lazy& lazy) {
            return mx2 < lazy.mn;
        }
    
        void upd(Lazy lazy, int sz) {
            if (lazy.mn < mx) sum -= (mx - lazy.mn) * mxcnt, mx = lazy.mn;
            sum += lazy.add * sz;
            mx += lazy.add, mx2 += lazy.add;
        }
    
        Value operator+(const Value& oth) const {
            Value res {};
            res.sum = sum + oth.sum;
            if (mx == oth.mx) res.mx = mx, res.mxcnt = mxcnt + oth.mxcnt, res.mx2 = max(mx2, oth.mx2);
            else if (mx > oth.mx) res.mx = mx, res.mxcnt = mxcnt, res.mx2 = max(mx2, oth.mx);
            else res.mx = oth.mx, res.mxcnt = oth.mxcnt, res.mx2 = max(mx, oth.mx2);
            return res;
        }
    };
    
    const Value vid = {0, -1'000'000'000'000'000'000, 0, -1'000'000'000'000'000'000};
    
    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    using ptr = struct Node*;
    
    struct Node {
        Value val;
        Value agg;
        Lazy lazy;
    
        int sz;
        int pri;
        ptr l, r;
    
        Node() {
            pri = mt();
            val = vid;
            agg = vid;
            lazy = lid;
            sz = 1;
            l = r = nullptr;
        }
    
        Node(Value val) : val(val), agg(val) {
            pri = mt();
            lazy = lid;
            sz = 1;
            l = r = nullptr;
        }
    
        ~Node() {
            delete l;
            delete r;
        }
    };
    
    int sz(ptr n) { return n ? n->sz : 0; };
    Value agg(ptr n) { return n ? n->agg : vid; }
    
    void push(ptr n) {
        n->val.upd(n->lazy, 1);
        n->agg.upd(n->lazy, sz(n));
        if (n->l) n->l->lazy += n->lazy;
        if (n->r) n->r->lazy += n->lazy;
        n->lazy = lid;
    }
    
    ptr pull(ptr n) {
        if (!n) return nullptr;
        if (n->l) push(n->l);
        if (n->r) push(n->r);
        n->sz = sz(n->l) + 1 + sz(n->r);
        n->agg = agg(n->l) + n->val + agg(n->r);
        return n;
    }
    
    ptr merge(ptr l, ptr r) {
        if (!l || !r) return l ? l : r;
        push(l), push(r);
        if (l->pri > r->pri) return l->r = merge(l->r, r), pull(l);
        else return r->l = merge(l, r->l), pull(r);
    }
    
    template<typename... Args>
    ptr merge(ptr l, Args... args) {
        return merge(l, merge(args...));
    }
    
    // [-inf, i) and [i, inf]
    pair<ptr, ptr> spliti(ptr n, int i) {
        if (!n) return {nullptr, nullptr};
        push(n);
        if (i <= sz(n->l)) {
            auto [l, r] = spliti(n->l, i);
            n->l = r;
            return {l, pull(n)};
        } else {
            auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
            n->r = l;
            return {pull(n), r};
        }
    }
    
    // cuts out [lo, hi)
    tuple<ptr, ptr, ptr> spliti(ptr n, int lo, int hi) {
        auto [lm, r] = spliti(n, hi);
        auto [l, m] = spliti(lm, lo);
        return {l, m, r};
    }
    
    void updi(ptr n, int lo, int hi, Lazy lazy) {
        if (!n) return;
        push(n);
        if (lo >= n->sz || hi <= 0 || n->agg.can_break(lazy)) return;
        if (lo <= 0 && n->sz <= hi && n->agg.can_tag(lazy)) {
            n->lazy += lazy;
            push(n);
            return;
        }
        if (lo <= sz(n->l) && sz(n->l) < hi) n->val.upd(lazy, 1);
        updi(n->l, lo, hi, lazy);
        updi(n->r, lo - 1 - sz(n->l), hi - 1 - sz(n->l), lazy);
        pull(n);
    }
    
    void heapify(ptr n) {
        if (!n) return;
        ptr mx = n;
        if (n->l && n->l->pri > mx->pri) mx = n->l;
        if (n->r && n->r->pri > mx->pri) mx = n->r;
        if (mx != n) swap(n->pri, mx->pri), heapify(mx);
    }
    
    ptr build(vector<ptr>& ns, int l = 0, int r = -69) {
        if (r == -69) r = (int) ns.size() - 1;
        if (l > r) return nullptr;
        if (l == r) return ns[l];
        int m = (l + r) / 2;
        ns[m]->l = build(ns, l, m - 1);
        ns[m]->r = build(ns, m + 1, r);
        heapify(ns[m]);
        return pull(ns[m]);
    }

}

using namespace Treap;

/*

- include n-way merge (and merge)
- include 3-way split by index (and size, and split by index)
- include build (and heapify)
- include range queries by index
- include range chmin and range add (and treap beats template, and range updates by index, and lazy prop, and range aggregates)
- use value type = long long

*/

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, q; 
    cin >> n >> q;

    vector<ptr> ns(n);
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        ns[i] = new Node(Value().make(x));
    }
    ptr treap = build(ns);

    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r, h; cin >> l >> r >> h;
            updi(treap, l - 1, r, chmin_tag(h));
        }
        if (t == 2) {
            int l, r; cin >> l >> r;
            auto [lhs, mid, rhs] = spliti(treap, l - 1, r);
            treap = merge(lhs, rhs, mid);
        }   
        if (t == 3) {
            int l, r, x; cin >> l >> r >> x;
            updi(treap, l - 1, r, add_tag(x));
        }
        push(treap);
        cout << agg(treap).sum << '\n';
    }
    delete treap;
}