/* j.cpp */
#include <bits/stdc++.h>

using i64 = long long;

constexpr int InputBufSize = 1 << 20;

inline char read_char() {
    static char buf[InputBufSize], *p1, *p2;
    static std::streambuf *inbuf = std::cin.rdbuf();
    return p1 == p2 && (p2 = (p1 = buf) + inbuf->sgetn(buf, InputBufSize), p1 == p2) ? EOF : *p1++;
}
template <typename T> void read(T &x) {
    x = 0; char c = read_char(); bool f = false;
    while (!isdigit(c)) f |= (c == '-'), c = read_char();
    while (isdigit(c)) x = x * 10 + c - '0', c = read_char();
    if (f) x *= -1;
}
inline void print_char(char c) {
    static std::streambuf *outbuf = std::cout.rdbuf();
    outbuf->sputc(c);
}
template <typename T> void print(T x) {
    if (x < 0) print_char('-'), x = -x;
    static char stk[50]; int top = 0;
    do stk[top++] = x % 10 + '0', x /= 10; while (x > 0);
    while (top--) print_char(stk[top]);
}

template <typename Info, typename Tag> struct LazySegmentTree {
    int n; std::vector<Info> s; std::vector<Tag> t;
    LazySegmentTree() : n{} {}
    LazySegmentTree(int n_, const Info &v = Info()) { init(n_, v); }
    template <typename T> LazySegmentTree(const std::vector<T> &ini) { init(ini); }
    void init(int n_, const Info &v = Info()) { init(std::vector(n_, v)); }
    template <typename T> void init(const std::vector<T> &ini) {
        n = int(ini.size());
        s.assign(4 << std::__lg(n), Info()), t.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int u, int l, int r) -> void {
            if (r - l == 1) return s[u] = ini[l], void();
            int m = (l + r) / 2;
            self(self, u << 1, l, m), self(self, u << 1 | 1, m, r), pull(u);
        };
        build(build, 1, 0, n);
    }
    void pull(int u) { s[u] = s[u << 1] + s[u << 1 | 1]; }
    void apply(int u, const Tag &v) { s[u].apply(v), t[u].apply(v); }
    void push(int u) { apply(u << 1, t[u]), apply(u << 1 | 1, t[u]), t[u] = Tag(); }
    void modify(int u, int l, int r, int p, const Info &v) {
        if (r - l == 1) return s[u] = v, void();
        int m = (l + r) / 2; push(u);
        if (p < m) modify(u << 1, l, m, p, v), pull(u);
        else modify(u << 1 | 1, m, r, p, v), pull(u);
    }
    void modify(int p, const Info &v) { modify(1, 0, n, p, v); }
    Info rangeQuery(int u, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return Info();
        if (ql <= l && r <= qr) return s[u];
        int m = (l + r) / 2; push(u);
        return rangeQuery(u << 1, l, m, ql, qr) + rangeQuery(u << 1 | 1, m, r, ql, qr);
    }
    Info rangeQuery(int ql, int qr) { return rangeQuery(1, 0, n, ql, qr); }
    void rangeApply(int u, int l, int r, int ql, int qr, const Tag &v) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) return apply(u, v);
        int m = (l + r) / 2; push(u);
        rangeApply(u << 1, l, m, ql, qr, v), rangeApply(u << 1 | 1, m, r, ql, qr, v);
        pull(u);
    }
    void rangeApply(int ql, int qr, const Tag &v) { rangeApply(1, 0, n, ql, qr, v); }
};

constexpr i64 inf = 1e18;

struct Tag {
    i64 d = 0, k = 1, b = 0;
    void apply(const Tag &y) & {
        d += y.d;
        b = y.k * b + y.b;
        k *= y.k;
    }
};

struct Info {
    int l1 = 0, l2 = 0; i64 mn = inf; int pos = -1;
    i64 s1 = 0, s2 = 0;
    void apply(const Tag &y) & {
        s1 -= l1 * y.d;
        mn -= y.d;
        s2 = y.k * s2 + 1ll * y.b * l2;
    }
};
Info operator+(const Info &x, const Info &y) {
    return {
        x.l1 + y.l1, x.l2 + y.l2,
        std::min(x.mn, y.mn), x.mn <= y.mn ? x.pos : y.pos,
        x.s1 + y.s1, x.s2 + y.s2
    };
}

void solve() {
    int n, m;
    read(n), read(m);

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        read(a[i]);
    }

    LazySegmentTree<Info, Tag> seg(n);
    for (int i = 0; i < n; ++i) {
        seg.modify(i, Info{1, 0, a[i], i, a[i], 0});
    }

    while (m--) {
        int op, l, r;
        read(op), read(l), read(r);
        --l;
        if (op == 1) {
            int x;
            read(x);
            while (seg.s[1].mn < x) {
                int p = seg.s[1].pos, x = seg.s[1].mn;
                seg.modify(p, Info{0, 1, inf, -1, 0, x});
            }
            seg.rangeApply(l, r, Tag{x, -1, x});
        }
        if (op == 2) {
            auto ans = seg.rangeQuery(l, r);
            print(ans.s1 + ans.s2), print_char('\n');
        }
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    read(t);

    while (t--) {
        solve();
    }

    return 0;
}