#include<bits/stdc++.h>

using namespace std;
#define rep2(i, j, k) for(ll i=ll(j);i<ll(k);i++)
#define rep(i, k) rep2(i,0,k)
#define rrep2(i, j, k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i, j) rrep2(i,j,0)
#define SZ(a) ll(a.size())
#define eb emplace_back
#define all(a) a.begin(),a.end()
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<ll, ll>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX / 4;

template<class T>
bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

template<class T>
bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

class lazy_segtree {
    using S = tuple<ll, int, ll, int>; // {sum, len, min, min_left_pos}
    const S e = {0, 0, inf, -1};

    S op(const S &l, const S &r) {
        auto [ls, llen, lm, lp] = l;
        auto [rs, rlen, rm, rp] = r;
        if (lm <= rm) return {ls + rs, llen + rlen, lm, lp};
        else return {ls + rs, llen + rlen, rm, llen + rp};
    }

    using F = P;
    const F id = {0, 0};

    F compose(const F &g, const F &f) {
        if (g.first) return g;
        return {f.first, f.second + g.second};
    }

    S mapping(const F &f, const S &x) {
        auto [s, len, m, p] = x;
        if (f.first) {
            return {f.second * len, len, f.second, 0};
        } else {
            return {s + f.second * len, len, m + f.second, p};
        }
    }

    int n, log;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < n) lz[k] = compose(f, lz[k]);
    }

    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id;
    }

public:
    lazy_segtree(const vector<S> &init) {
        log = 0;
        while (1 << log < SZ(init)) log++;
        n = 1 << log;
        d.assign(2 * n, e);
        lz.assign(n, id);
        rep(i, SZ(init)) d[n + i] = init[i];
        rrep2(i, n, 1) update(i);
    }

    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);

        l += n, r += n;

        rrep2(i, log + 1, 1) {
            if ((l >> i) << i != l) push(l >> i);
            if ((r >> i) << i != r) push(r >> i);
        }

        S sl = e, sr = e;
        while (l < r) {
            if (l & 1) sl = op(sl, d[l++]);
            if (r & 1) sr = op(d[--r], sr);
            l >>= 1, r >>= 1;
        }

        return op(sl, sr);
    }

    void apply(int l, int r, F f) {
        assert(0 <= l and l <= r and r <= n);

        l += n, r += n;

        rrep2(i, log + 1, 1) {
            if ((l >> i) << i != l) push(l >> i);
            if ((r >> i) << i != r) push(r >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1, r >>= 1;
            }
            l = l2, r = r2;
        }

        rep2(i, 1, log + 1) {
            if ((l >> i) << i != l) update(l >> i);
            if ((r >> i) << i != r) update(r >> i);
        }
    }

    template<class F>
    int max_right(int l, F f) {
        assert(0 <= l && l <= n);
        assert(f(e));
        if (l == n) return n;
        l += n;
        rrep2(i, log + 1, 1) push(l >> i);
        S now = e;
        do {
            while (~l & 1) l >>= 1;
            if (!f(op(now, d[l]))) {
                while (l < n) {
                    push(l);
                    l *= 2;
                    if (f(op(now, d[l]))) {
                        now = op(now, d[l]);
                        ++l;
                    }
                }
                return l - n;
            }
            now = op(now, d[l]);
            ++l;
        } while ((l & -l) != l);
        return n;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);
    int n, m;
    cin >> n >> m;
    vector<tuple<ll, int, ll, int>> init(n);
    rep(i, n) {
        ll a;
        cin >> a;
        init[i] = {a, 1, a, 0};
    }
    lazy_segtree st(init);
    rep(_, m) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, v;
            cin >> l >> r >> v;
            --l;
            st.apply(l, r, P(1, v));
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;
            --l;
            ll mex = 0;
            vector<tuple<int, int, ll>> ls;
            while (true) {
                auto [_, _2, mn, nl] = st.prod(l, r);
                nl += l;
                if (mn > mex) break;
                assert(mn == mex - 1 or mn == mex);
                if (mn == mex) ++mex;
                int nr = st.max_right(nl, [&](auto t) {
                    return get<0>(t) == get<2>(t) * get<1>(t);
                });
                chmin(nr, r);
                ls.eb(nl, nr, mn);
                st.apply(nl, nr, P(1, inf));
            }
            for (auto [nl, nr, val]: ls) {
                st.apply(nl, nr, P(1, val));
            }
            st.apply(l, r, P(0, mex));
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            cout << get<0>(st.prod(l, r)) << '\n';
        }
    }
}