#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using ll = long long;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];


struct ST {
    struct Node {
        int l, r;
        ll sum;
    };
    vector<Node> tr;

    ST(const ST& other) : tr(other.tr) { }
    ST(ST&& other) noexcept : tr(move(other.tr)) { }
    ST (int l, int r) : tr(vector<Node>(((r - l + 1) << 2) + 10)) { build(1, l, r); }

    ST& operator=(ST&& other) noexcept {
        if (this != &other) {
            tr = move(other.tr);
        }
        return *this;
    }
    ST& operator=(const ST& other) {  
        if (this != &other) {  
            tr = other.tr;
        }  
        return *this;  
    }

    void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }

    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }

    ll query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if (l <= mid) res += query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }

    void modify(int u, int x, ll v) {
        if (tr[u].l == tr[u].r) tr[u].sum += v;
        else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            if (x > mid) modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }
};

void solve() {
    set<array<int, 3> > st;
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i < n + 1; i++) {
        scanf("%d", &x);
        st.insert({i, 1, x});
    }
    ST tr(1, n);
    for (auto u : st) tr.modify(1, u[0], u[2]);
    while (m--) {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        ++l;
        if (op == 0) {
            if (l > r) {
                puts("0");
                continue;
            }
            ll sum = tr.query(1, l, r);
            auto u = st.lower_bound({l, -1, -1});
            if (u != st.begin()) {
                --u;
                int v = (*u)[2], p = (*u)[0], c = (*u)[1];
                if (p + c - 1 >= l) {
                    sum += min(p + c - l, r - l + 1) * (ll)v;
                }
            }
            u = st.lower_bound({r + 1, -1, -1});
            if (u != st.begin()) {
                --u;
                int v = (*u)[2], p = (*u)[0], c = (*u)[1];
                if (p >= l && p + c - 1 > r) {
                    sum -= (p + c - 1 - r) * (ll)v;
                }
            }
            printf("%lld\n", sum);
        } else if (op == 1) {
            scanf("%d", &x);
            if (l > r) continue;
            while (1) {
                auto u = st.lower_bound({l, -1, -1});
                if (u == st.end() || (*u)[0] > r) break;
                auto t = *u;
                tr.modify(1, t[0], -(ll)t[1] * t[2]);
                st.erase(u);
                if (t[0] + t[1] - 1 > r) {
                    t[1] -= r - t[0] + 1, t[0] = r + 1;
                    st.insert(t);
                    tr.modify(1, t[0], (ll)t[1] * t[2]);
                }
            }
            auto u = st.lower_bound({l, -1, -1});
            if (u != st.begin()) {
                --u;
                int v = (*u)[2], p = (*u)[0], c = (*u)[1];
                if (p + c - 1 >= l) {
                    tr.modify(1, p, -(ll)v * c);
                    st.erase(u);
                    st.insert({p, l - p, v});
                    tr.modify(1, p, (ll)v * (l - p));
                    if (p + c - 1 > r) {
                        st.insert({r + 1, p + c - 1 - r, v});
                        tr.modify(1, r + 1, (ll)v * (p + c - 1 - r));
                    }
                }
            }
            st.insert({l, r - l + 1, x});
            tr.modify(1, l, (ll)(r - l + 1) * x);
        } else {
            if (l > r) continue;
            vector<array<int, 3>> q;
            while (1) {
                auto u = st.lower_bound({l, -1, -1});
                if (u == st.end() || (*u)[0] > r) break;
                auto t = *u;
                tr.modify(1, t[0], -(ll)t[1] * t[2]);
                st.erase(u);
                if (t[0] + t[1] - 1 > r) {
                    auto g = t;
                    g[1] -= r - g[0] + 1, g[0] = r + 1;
                    st.insert(g);
                    tr.modify(1, g[0], (ll)g[1] * g[2]);
                }
                t[1] = min(t[1], r - t[0] + 1), t[2] = sqrt(t[2]);
                q.push_back(t);
                tr.modify(1, t[0], (ll)t[1] * t[2]);
            }
            for (auto u : q) st.insert(u);

            auto u = st.lower_bound({l, -1, -1});
            if (u != st.begin()) {
                --u;
                int v = (*u)[2], p = (*u)[0], c = (*u)[1];
                if (p + c - 1 >= l) {
                    array<int, 3> t = {l, min(r - l + 1, p + c - l), v};
                    tr.modify(1, p, -(ll)v * c);
                    st.erase(u);
                    st.insert({p, l - p, v});
                    tr.modify(1, p, (ll)v * (l - p));
                    if (p + c - 1 > r) {
                        st.insert({r + 1, p + c - 1 - r, v});
                        tr.modify(1, r + 1, (ll)v * (p + c - 1 - r));
                    }

                    t[2] = sqrt(t[2]);
                    st.insert(t);
                    tr.modify(1, t[0], (ll)t[1] * t[2]);
                }
            }

            u = st.lower_bound({l, -1, -1});
            if (u != st.begin()) --u;
            while (u != st.end() && (*u)[0] <= r) {
                while (1) {
                    auto t = u;
                    ++t;
                    if (t != st.end() && ((*t)[2] == (*u)[2])) {
                        int v = (*t)[2], p = (*t)[0], c = (*t)[1];
                        tr.modify(1, p, (ll)-v * c);
                        st.erase(t);
                        auto g = *u;
                        tr.modify(1, g[0], -(ll)g[1] * g[2]);
                        st.erase(u);
                        g[1] += c;
                        u = st.insert(g).first;
                        tr.modify(1, g[0], (ll)g[1] * g[2]);
                    } else break;
                }
                ++u;
            }
        }
    }
}

void s2() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i < n + 1; i++) {
        scanf("%d", w + i);
    }
    while (m--) {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        ++l;

        if (op == 0) {
            if (l > r) {
                puts("0");
                continue;
            }
            ll sum = 0;
            for (int i = l; i <= r; i++) sum += w[i];
            printf("%lld\n", sum);
        } else if (op == 1) {
            scanf("%d", &x);
            if (l > r) continue;
            for (int i = l; i <= r; i++) w[i] = x;
        } else {
            if (l > r) continue;
            for (int i = l; i <= r; i++) w[i] = sqrt(w[i]);
        }
    }
}

int main() {
    int T = 1;
    // cin >> T;
    // while (T--) s2();
    while (T--) solve();
    return 0;
}