#include <algorithm>
#include <cstdio>
#include <queue>

#define ls(o) o << 1
#define rs(o) o << 1 | 1

constexpr int MAXN = 500000 + 2;
constexpr int MAXLOGN = 18 + 2;

class Tag {
  public:
    int addVal, assignVal;

    Tag& operator +=(const Tag &rhs) {
        if (rhs.assignVal >= 0) {
            assignVal = rhs.assignVal;
            addVal = 0;
        }
        addVal += rhs.addVal;

        return *this;
    }
};

class Triple {
  public:
    int o, l, r;
};

class Node {
  public:
    int maxVal, minVal, p, len;
    long long sum;

    Node operator +(const Node &rhs) const {
        return {
          std::max(maxVal, rhs.maxVal),
          std::min(minVal, rhs.minVal),
          minVal < rhs.minVal ? p : rhs.p,
          len + rhs.len,
          sum + rhs.sum
        };
    }

    Node operator +=(const Tag &tag) {
        if (tag.assignVal >= 0) {
            maxVal = minVal =
              tag.assignVal + tag.addVal;
            sum = (long long){maxVal} * len;
        } else {
            maxVal += tag.addVal;
            minVal += tag.addVal;
            sum += (long long){tag.addVal} * len;
        }

        return *this;
    }
};

class SegmentTree {
  public:
    int n;
    Node t[MAXN << 2];
    Tag tag[MAXN << 2];

    void push(int o, const Tag &tg, int l) {
        t[o] += tg;
        tag[o] += tg;

        if (t[o].maxVal == t[o].minVal) {
            t[o].p = l;
        }
    }

    void pushDown(int o, int l, int r) {
        if (!tag[o].addVal &&
          tag[o].assignVal < 0) {
            return;
        }

        int mid = (l + r) >> 1;

        push(ls(o), tag[o], l);
        push(rs(o), tag[o], mid);

        tag[o] = {0, -1};
    }

    void pushUp(int o) {
        t[o] = t[ls(o)] + t[rs(o)];
    }

    void build(int o, int l, int r) {
        tag[o] = {0, -1};

        if (l == r) {
            scanf("%d", &t[o].maxVal);
            t[o].sum = t[o].minVal = t[o].maxVal;
            t[o].p = l;
            t[o].len = 1;

            return;
        }

        int mid = (l + r) >> 1;

        build(ls(o), l, mid);
        build(rs(o), mid + 1, r);

        pushUp(o);
    }

    void build(int _n) {
        build(1, 1, n = _n);
    }

    void update(
      int o, int l, int r,
      int x, int y, const Tag &tg
    ) {
        if (x <= l && r <= y) {
            return push(o, tg, l);
        }

        pushDown(o, l, r);
        int mid = (l + r) >> 1;

        if (x <= mid) {
            update(ls(o), l, mid, x, y, tg);
        }
        if (y > mid) {
            update(rs(o), mid + 1, r, x, y, tg);
        }

        pushUp(o);
    }

    void assign(int l, int r, int v) {
        update(1, 1, n, l, r, {0, v});
    }

    void add(int l, int r, int v) {
        update(1, 1, n, l, r, {v, -1});
    }

    Node query(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return t[o];
        }

        pushDown(o, l, r);
        int mid = (l + r) >> 1;

        if (y <= mid) {
            return query(ls(o), l, mid, x, y);
        }
        if (x > mid) {
            return query(rs(o), mid + 1, r, x, y);
        }
        return query(ls(o), l, mid, x, y)
          + query(rs(o), mid + 1, r, x, y);
    }

    Node query(int l, int r) {
        return query(1, 1, n, l, r);
    }

    int right(int x, int v) {
        static Triple stk[MAXLOGN];
        int o = 1, l = 1, r = n, top = 0;

        while (l < r) {
            pushDown(o, l, r);
            int mid = (l + r) >> 1;

            if (x > mid) {
                o = rs(o);
                l = mid + 1;
            } else {
                stk[++ top] = {rs(o), mid + 1, r};
                o = ls(o);
                r = mid;
            }
        }

        while (top) {
            o = stk[top].o;
            if (t[o].minVal < t[o].maxVal
              || t[o].minVal != v) {
                break;
            }
            top --;
        }

        if (!top) {
            return n + 1;
        }

        l = stk[top].l;
        r = stk[top].r;

        while (l < r) {
            pushDown(o, l, r);
            int mid = (l + r) >> 1;
            Node u = t[ls(o)];

            if (u.minVal < u.maxVal || u.minVal != v) {
                o = ls(o);
                r = mid;
            } else {
                o = rs(o);
                l = mid + 1;
            }
        }

        return l;
    }
} segTree;

class Info {
  public:
    int l, r, minVal, p;

    Info(int _l, int _r) {
        Node tmp = segTree.query(l = _l, r = _r);
        minVal = tmp.minVal;
        p = tmp.p;
    }

    bool operator <(const Info &rhs) const {
        return minVal > rhs.minVal;
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    segTree.build(n);

    while (m --) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);

        if (op == 1) {
            int v;
            scanf("%d", &v);

            segTree.assign(l, r, v);
        }

        if (op == 2) {
            int delta = -1, p;

            std::priority_queue<Info> q;
            q.push(Info(l, r));

            while (q.size()) {
                Info iv = q.top();
                q.pop();

                if (iv.minVal > delta + 1) {
                    break;
                }
                delta = iv.minVal;

                if (iv.p > iv.l) {
                    q.push(Info(iv.l, iv.p - 1));
                }
                if ((p = segTree.right(iv.p, delta)) <= iv.r) {
                    q.push(Info(p, iv.r));
                }
            }

            if (delta >= 0) {
                segTree.add(l, r, delta + 1);
            }
        }

        if (op == 3) {
            printf("%lld\n", segTree.query(l, r).sum);
        }
    }

    return 0;
}