#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;
#define ll long long
const int INF = 1e9;

struct Node {
    ll sum;
    int mx, mn;
    int push_set, push_plus;
};

Node get_empty() {
    return {0, -INF, INF, -1, -1};
}

Node merge(const Node& a, const Node& b) {
    Node ans;
    ans.sum = a.sum + b.sum;
    ans.mx = max(a.mx, b.mx);
    ans.mn = min(a.mn, b.mn);
    ans.push_plus = 0;
    ans.push_set = -1;
    return ans;
}

struct SegTree {
    int n;
    vector <Node> t;


    SegTree(int n, const vector <int>& a) : n(n) {
        t.resize(4 * n);
        build(1, 0, n - 1, a);
    }

    void build(int v, int l, int r, const vector <int>& a) {
        if (l == r) {
            t[v].sum = t[v].mx = t[v].mn = a[l];
            t[v].push_set = -1;
            t[v].push_plus = 0;
            return;
        }
        int m = (l + r) / 2;
        build(2 * v, l, m, a);
        build(2 * v + 1, m + 1, r, a);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }

    void make_plus(int v, int l, int r, int x) {
        t[v].mn += x;
        t[v].mx += x;
        t[v].sum += 1ll * (r - l + 1) * x;
        if (t[v].push_set != -1) t[v].push_set += x;
        else t[v].push_plus += x;
    }

    void make_set(int v, int l, int r, int x) {
        t[v].mn = t[v].mx = x;
        t[v].sum = 1ll * (r - l + 1) * x;
        t[v].push_set = x;
        t[v].push_plus = 0;
    }

    inline void push(int v, int l, int r) {
        int m = (l + r) / 2;
        if (t[v].push_set != -1) {
            make_set(2 * v, l, m, t[v].push_set);
            make_set(2 * v + 1, m + 1, r, t[v].push_set);
            t[v].push_set = -1;
        } else if (t[v].push_plus != 0) {
            make_plus(2 * v, l, m, t[v].push_plus);
            make_plus(2 * v + 1, m + 1, r, t[v].push_plus);
            t[v].push_plus = 0;
        }
    }

    void set_seg(int v, int l, int r, int A, int B, int x) {
        if (l > B || A > r) return;
        if (A <= l && r <= B) {
            make_set(v, l, r, x);
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2;
        set_seg(2 * v, l, m, A, B, x);
        set_seg(2 * v + 1, m + 1, r, A, B, x);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }

    void add_seg(int v, int l, int r, int A, int B, int x) {
        if (l > B || A > r) return;
        if (A <= l && r <= B) {
            make_plus(v, l, r, x);
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2;
        add_seg(2 * v, l, m, A, B, x);
        add_seg(2 * v + 1, m + 1, r, A, B, x);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }

    int get_min(int v, int l, int r, int A, int B) {
        if (l > B || A > r) return INF;
        if (A <= l && r <= B) return t[v].mn;
        push(v, l, r);
        int m = (l + r) / 2;
        return min(get_min(2 * v, l, m, A, B), get_min(2 * v + 1, m + 1, r, A, B));
    }

    ll get_sum(int v, int l, int r, int A, int B) {
        if (l > B || A > r) return 0;
        if (A <= l && r <= B) return t[v].sum;
        int m = (l + r) / 2;
        push(v, l, r);
        return get_sum(2 * v, l, m, A, B) + get_sum(2 * v + 1, m + 1, r, A, B);
    }

    int find_pos_min(int v, int l, int r, int A, int B, int x) {
        if (l > B || A > r || t[v].mn != x) return -1;
        if (l == r) return l;
        push(v, l, r);
        int m = (l + r) / 2;
        int lft = find_pos_min(2 * v, l, m, A, B, x);
        if (lft != -1) return lft;
        return find_pos_min(2 * v + 1, m + 1, r, A, B, x);
    }

    int first_more(int v, int l, int r, int A, int B, int x) {
        if (l > B || A > r || t[v].mx <= x) return -1;
        if (l == r) return l;
        int m = (l + r) / 2;
        push(v, l, r);
        int lft = first_more(2 * v, l, m, A, B, x);
        if (lft != -1) return lft;
        return first_more(2 * v + 1, m + 1, r, A, B, x);
    }

    int last_more(int v, int l, int r, int A, int B, int x) {
        if (l > B || A > r || t[v].mx <= x) return -1;
        if (l == r) return l;
        int m = (l + r) / 2;
        push(v, l, r);
        int rgt = last_more(2 * v + 1, m + 1, r, A, B, x);
        if (rgt != -1) return rgt;
        return last_more(2 * v, l, m, A, B, x);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    SegTree t(n, a);
    vector <array <int, 3>> st;
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, v;
            cin >> l >> r >> v; --l; --r;
            t.set_seg(1, 0, n - 1, l, r, v);
        } else if (op == 2) {
            int l, r;
            cin >> l >> r; --l; --r;
            int mex = 0;

            for (int val = 0;; ++val) {
                int my_min = t.get_min(1, 0, n - 1, l, r);

                if (my_min != val) {
                    mex = val;
                    break;
                }

                while (my_min == val) {
                    int l_pos = t.find_pos_min(1, 0, n - 1, l, r, val);
                    int r_bad = t.first_more(1, 0, n - 1, l_pos, r, val);
                    if (r_bad == -1) r_bad = r + 1;
                    r_bad--;

                    st.push_back({l_pos, r_bad, val});
                    t.set_seg(1, 0, n - 1, l_pos, r_bad, INF);
                    my_min = t.get_min(1, 0, n - 1, l, r);
                }
            }

            for (auto i : st) {
                t.set_seg(1, 0, n - 1, i[0], i[1], i[2]);
            }
            st.clear();
            t.add_seg(1, 0, n - 1, l, r, mex);
        } else {
            int l, r;
            cin >> l >> r; --l; --r;
            cout << t.get_sum(1, 0, n - 1, l, r) << "\n";
        }
    }
}

signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
 */