#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define N 500010

int n, m;
ll a[N];
ll sum[N << 2], tadd[N << 2], tval[N << 2];
ll mn[N << 2];
int len[N << 2];

#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
int st[N], top;

void pushup(int x) 
{
    sum[x] = sum[ls] + sum[rs];
    len[x] = len[ls] + len[rs];
    mn[x] = min(mn[ls], mn[rs]);
}

void push(int x, int tgadd, int tgval)
{
    if (tgval != -1)
    {
        sum[x] = 1LL * len[x] * tgval, mn[x] = tgval;
        tadd[x] = 0, tval[x] = tgval;
    }
    sum[x] += 1LL * len[x] * tgadd; mn[x] += tgadd;
    tadd[x] += tgadd;
}
void pushdown(int x)
{
    push(ls, tadd[x], tval[x]); push(rs, tadd[x], tval[x]);
    tadd[x] = 0, tval[x] = -1;
}



void build(int l, int r, int x)
{
    tadd[x] = 0, tval[x] = -1;
    if (l == r) {sum[x] = mn[x] = a[l]; len[x] = 1; return ;}
    build(l, mid, ls); build(mid + 1, r, rs);
    pushup(x);
}
void upd(int l, int r, int x, int ql, int qr, pair<int, int>tg)
{
    if (l == ql && r == qr) {push(x, tg.first, tg.second); return ;}

    pushdown(x);
    if (qr <= mid)upd(l, mid, ls, ql, qr, tg);
    else if (ql > mid)upd(mid + 1, r, rs, ql, qr, tg);
    else {upd(l, mid, ls, ql, mid, tg); upd(mid + 1, r, rs, mid + 1, qr, tg);}

    pushup(x);
}
ll qry(int l, int r, int x, int ql, int qr)
{
    if (l == ql && r == qr)return sum[x];
    pushdown(x);

    if (qr <= mid)return qry(l, mid, ls, ql, qr);
    else if (ql > mid)return qry(mid + 1, r, rs, ql, qr);
    else return qry(l, mid, ls, ql, mid) + qry(mid + 1, r, rs, mid + 1, qr);
}
void Find(int l, int r, int x, int ql, int qr)
{
    if (l == ql && r == qr){st[++ top] = x; return ;}
    pushdown(x);

    if (qr <= mid)Find(l, mid, ls, ql, qr);
    else if (ql > mid)Find(mid + 1, r, rs, ql, qr);
    else {Find(l, mid, ls, ql, mid), Find(mid + 1, r, rs, mid + 1, qr);}
}
void sol()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)cin >> a[i];
    build(1, n, 1);

    while (m --)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, v;
            cin >> l >> r >> v;
            upd(1, n, 1, l, r, {0, v});
        }
        else if (op == 2)
        {
            int l, r;
            cin >> l >> r;
            top = 0;
            Find(1, n, 1, l, r);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
            for (int i = 1; i <= top; i ++)q.push({mn[st[i]], st[i]});
            int ansv = 0; bool flag = 0;
            while (!q.empty())
            {
                int x = q.top().second; q.pop();
                // cout << "??:" << x << ' ' << len[x] << ' ' << mn[x] << endl;
                if (mn[x] == ansv) {flag = 1;}
                else if (mn[x] > ansv)
                {
                    if (flag) {++ ansv; flag = 0; q.push({mn[x], x}); continue;}
                    else break;
                }

                if (len[x] > 1)
                {
                    pushdown(x);
                    q.push({mn[ls], ls});
                    q.push({mn[rs], rs});
                }
            }

            if (flag) ++ ansv;
            // cout << "EE:" << l << ' ' << r << ' ' << ansv << endl;

            upd(1, n, 1, l, r, {ansv, -1});

        }
        else if (op == 3)
        {
            int l, r;
            cin >> l >> r;
            cout << qry(1, n, 1, l, r) << '\n';
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T --) sol();

    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
*/