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

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

constexpr int MAXN = 500000 + 2;

int a[MAXN];

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 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) {
        t[o] += tg;
        tag[o] += tg;
    }

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

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

        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);
        }

        pushDown(o);
        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);
        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);
    }
} segTree;

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

    Info(int _l, int _r) {
        Node tmp = segTree.query(l = _l, r = _r);
        maxVal = tmp.maxVal;
        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;

            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.minVal == iv.maxVal) {
                    continue;
                }

                if (iv.p > iv.l) {
                    q.push(Info(iv.l, iv.p - 1));
                }
                if (iv.p < iv.r) {
                    q.push(Info(iv.p + 1, iv.r));
                }
            }

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

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

    return 0;
}