#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define X first
#define Y second

const ll mod = 1000000007;

ll pew(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}

ll t[1200000], cnt[1200000], del[1200000], F[1200000];
pair<ll,ll> mn[1200000];

vector<int> a;

void push(int v)
{
    for (int j=v*2;j<=v*2+1;j++)
    {
        del[j] += del[v];
        t[j] += del[v]*cnt[j];
        mn[j].X += del[v];
    }
    del[v] = 0;
}

void recalc(int v)
{
    cnt[v] = cnt[v*2]+cnt[v*2+1];
    t[v] = t[v*2]+t[v*2+1];
    mn[v] = min(mn[v*2],mn[v*2+1]);
}

void push2(int v)
{
    if (F[v]==0)
    {
        for (int j=v*2;j<=v*2+1;j++)
        {
            del[j] += del[v];
            t[j] += del[v]*cnt[j];
        }
        del[v] = 0;
        return;
    }
    for (int j=v*2;j<=v*2+1;j++)
    {
        del[j] = del[v]-del[j];
        t[j] = del[v]*cnt[j]-t[j];
        F[j] ^= 1;
    }
    del[v] = F[v] = 0;
}

void build(int v, int tl, int tr)
{
    t[v] = cnt[v] = del[v] = 0;
    if (tl==tr)
    {
        mn[v] = {a[tl],tl};
        t[v] = a[tl];
        cnt[v] = 1;
        return;
    }
    int tm = (tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    recalc(v);
}

void build2(int v, int tl, int tr)
{
    t[v] = cnt[v] = del[v] = F[v] = 0;
    if (tl==tr) return;
    int tm = (tl+tr)/2;
    build2(v*2,tl,tm);
    build2(v*2+1,tm+1,tr);
}

pair<ll,ll> get(int v, int tl, int tr, int l, int r)
{
    if (tl>=l and tr<=r) return mn[v];
    int tm = (tl+tr)/2;
    push(v);
    pair<ll,ll> x = {mod*mod,-1};
    if (tm>=l) x = min(x,get(v*2,tl,tm,l,r));
    if (tm<r) x = min(x,get(v*2+1,tm+1,tr,l,r));
    return x;
}

void err(int v, int v2, int tl, int tr, int p)
{
    if (tl==tr)
    {
        mn[v] = {mod*mod,tl};
        t[v2] = t[v];
        t[v] = cnt[v] = 0;
        cnt[v2] = 1;
        return;
    }
    push(v);
    push2(v2);
    int tm = (tl+tr)/2;
    if (tm>=p) err(v*2,v2*2,tl,tm,p);
    else err(v*2+1,v2*2+1,tm+1,tr,p);
    recalc(v);
    cnt[v2] = cnt[v2*2]+cnt[v2*2+1];
    t[v2] = t[v2*2]+t[v2*2+1];
}

void upd(int v, int tl, int tr, int l, int r, ll x)
{
    if (tl>=l and tr<=r)
    {
        t[v] -= cnt[v]*x;
        mn[v].X -= x;
        del[v] -= x;
        return;
    }
    push(v);
    int tm = (tl+tr)/2;
    if (tm>=l) upd(v*2,tl,tm,l,r,x);
    if (tm<r) upd(v*2+1,tm+1,tr,l,r,x);
    recalc(v);
}

void upd2(int v, int tl, int tr, int l, int r, ll x)
{
    if (tl>=l and tr<=r)
    {
        t[v] = x*cnt[v]-t[v];
        del[v] = x-del[v];
        F[v] ^= 1;
        return;
    }
    push2(v);
    int tm = (tl+tr)/2;
    if (tm>=l) upd2(v*2,tl,tm,l,r,x);
    if (tm<r) upd2(v*2+1,tm+1,tr,l,r,x);
    t[v] = t[v*2]+t[v*2+1];
}

ll calc(int v, int v2, int tl, int tr, int l, int r)
{
    if (tl>=l and tr<=r) return t[v]+t[v2];
    int tm = (tl+tr)/2;
    push(v);
    push2(v2);
    ll S = 0;
    if (tm>=l) S += calc(v*2,v2*2,tl,tm,l,r);
    if (tm<r) S += calc(v*2+1,v2*2+1,tm+1,tr,l,r);
    return S;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    a.resize(n);
    for (ll i=0;i<n;i++) cin >> a[i];
    build(2,0,n-1);
    build2(3,0,n-1);
    while (m--)
    {
        ll T;
        cin >> T;
        if (T==2)
        {
            ll L, R;
            cin >> L >> R;
            L--, R--;
            cout << calc(2,3,0,n-1,L,R) << "\n";
            continue;
        }
        ll L, R, x;
        cin >> L >> R >> x;
        L--, R--;
        while (true)
        {
            pair<ll,ll> w = get(2,0,n-1,L,R);
            if (w.X>x) break;
            err(2,3,0,n-1,w.Y);
        }
        upd(2,0,n-1,L,R,x);
        upd2(3,0,n-1,L,R,x);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    //freopen("input.txt", "r", stdin);
#endif
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}