#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int n, q, T, arr[MAX];
long long tree[MAX << 2], lazy[MAX << 2];
void Build(int id = 1, int L = 1, int R = n){
if(L == R){
tree[id] = arr[L];
return;
}
int mid = (L + R) >> 1;
Build(id << 1, L, mid);
Build(id << 1 | 1, mid + 1, R);
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
void Propagate(int id, int L, int mid, int R){
if(!lazy[id])
return;
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
tree[id << 1] += 1ll * (mid - L + 1) * lazy[id];
tree[id << 1 | 1] += 1ll * (R - mid) * lazy[id];
lazy[id] = 0;
}
void UpdateSqrt(int st, int en, int id = 1, int L = 1, int R = n){
if(tree[id] == R - L + 1)
return;
if(L == R){
tree[id] = sqrt(tree[id]);
return;
}
int mid = (L + R) >> 1;
Propagate(id, L, mid, R);
if(st <= mid)
UpdateSqrt(st, en, id << 1, L, mid);
if(en > mid)
UpdateSqrt(st, en, id << 1 | 1, mid + 1, R);
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
void UpdateRange(int st, int en, int val, int id = 1, int L = 1, int R = n){
if(st > R || L > en)
return;
if(st <= L && R <= en){
tree[id] += 1ll * (R - L + 1) * val;
lazy[id] += val;
return;
}
int mid = (L + R) >> 1;
Propagate(id, L, mid, R);
UpdateRange(st, en, val, id << 1, L, mid);
UpdateRange(st, en, val, id << 1 | 1, mid + 1, R);
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
long long Query(int st, int en, int id = 1, int L = 1, int R = n){
if(st <= L && R <= en)
return tree[id];
int mid = (L + R) >> 1;
Propagate(id, L, mid, R);
if(en <= mid)
return Query(st, en, id << 1, L, mid);
if(st > mid)
return Query(st, en, id << 1 | 1, mid + 1, R);
return Query(st, en, id << 1, L, mid) + Query(st, en, id << 1 | 1, mid + 1, R);
}
int main(){
scanf("%d", &T);
while(T--) {
memset(lazy, 0, sizeof lazy);
memset(tree, 0, sizeof tree);
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", arr + i);
Build();
while (q--){
int t, L, R, x;
scanf("%d %d %d", &t, &L, &R);
if (t == 1)
UpdateSqrt(L, R);
else if(t == 2)
printf("%lld\n", Query(L, R));
else if(t == 3){
scanf("%d", &x);
UpdateRange(L, R, x);
}
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBNQVggPSAxZTUgKyA1OwoKaW50IG4sIHEsIFQsIGFycltNQVhdOwpsb25nIGxvbmcgdHJlZVtNQVggPDwgMl0sIGxhenlbTUFYIDw8IDJdOwoKdm9pZCBCdWlsZChpbnQgaWQgPSAxLCBpbnQgTCA9IDEsIGludCBSID0gbil7CiAgICBpZihMID09IFIpewogICAgICAgIHRyZWVbaWRdID0gYXJyW0xdOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSAoTCArIFIpID4+IDE7CiAgICBCdWlsZChpZCA8PCAxLCBMLCBtaWQpOwogICAgQnVpbGQoaWQgPDwgMSB8IDEsIG1pZCArIDEsIFIpOwogICAgdHJlZVtpZF0gPSB0cmVlW2lkIDw8IDFdICsgdHJlZVtpZCA8PCAxIHwgMV07Cn0KCgp2b2lkIFByb3BhZ2F0ZShpbnQgaWQsIGludCBMLCBpbnQgbWlkLCBpbnQgUil7CiAgICBpZighbGF6eVtpZF0pCiAgICAgICAgcmV0dXJuOwogICAgbGF6eVtpZCA8PCAxXSArPSBsYXp5W2lkXTsKICAgIGxhenlbaWQgPDwgMSB8IDFdICs9IGxhenlbaWRdOwogICAgdHJlZVtpZCA8PCAxXSArPSAxbGwgKiAobWlkIC0gTCArIDEpICogbGF6eVtpZF07CiAgICB0cmVlW2lkIDw8IDEgfCAxXSArPSAxbGwgKiAoUiAtIG1pZCkgKiBsYXp5W2lkXTsKICAgIGxhenlbaWRdID0gMDsKfQoKdm9pZCBVcGRhdGVTcXJ0KGludCBzdCwgaW50IGVuLCBpbnQgaWQgPSAxLCBpbnQgTCA9IDEsIGludCBSID0gbil7CiAgICBpZih0cmVlW2lkXSA9PSBSIC0gTCArIDEpCiAgICAgICAgcmV0dXJuOwogICAgaWYoTCA9PSBSKXsKICAgICAgICB0cmVlW2lkXSA9IHNxcnQodHJlZVtpZF0pOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSAoTCArIFIpID4+IDE7CiAgICBQcm9wYWdhdGUoaWQsIEwsIG1pZCwgUik7CiAgICBpZihzdCA8PSBtaWQpCiAgICAgICAgVXBkYXRlU3FydChzdCwgZW4sIGlkIDw8IDEsIEwsIG1pZCk7CiAgICBpZihlbiA+IG1pZCkKICAgICAgICBVcGRhdGVTcXJ0KHN0LCBlbiwgaWQgPDwgMSB8IDEsIG1pZCArIDEsIFIpOwogICAgdHJlZVtpZF0gPSB0cmVlW2lkIDw8IDFdICsgdHJlZVtpZCA8PCAxIHwgMV07Cn0KCnZvaWQgVXBkYXRlUmFuZ2UoaW50IHN0LCBpbnQgZW4sIGludCB2YWwsIGludCBpZCA9IDEsIGludCBMID0gMSwgaW50IFIgPSBuKXsKICAgIGlmKHN0ID4gUiB8fCBMID4gZW4pCiAgICAgICAgcmV0dXJuOwogICAgaWYoc3QgPD0gTCAmJiBSIDw9IGVuKXsKICAgICAgICB0cmVlW2lkXSArPSAxbGwgKiAoUiAtIEwgICsgMSkgKiB2YWw7CiAgICAgICAgbGF6eVtpZF0gKz0gdmFsOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSAoTCArIFIpID4+IDE7CiAgICBQcm9wYWdhdGUoaWQsIEwsIG1pZCwgUik7CiAgICBVcGRhdGVSYW5nZShzdCwgZW4sIHZhbCwgaWQgPDwgMSwgTCwgbWlkKTsKICAgIFVwZGF0ZVJhbmdlKHN0LCBlbiwgdmFsLCBpZCA8PCAxIHwgMSwgbWlkICsgMSwgUik7CiAgICB0cmVlW2lkXSA9IHRyZWVbaWQgPDwgMV0gKyB0cmVlW2lkIDw8IDEgfCAxXTsKfQoKbG9uZyBsb25nIFF1ZXJ5KGludCBzdCwgaW50IGVuLCBpbnQgaWQgPSAxLCBpbnQgTCA9IDEsIGludCBSID0gbil7CiAgICBpZihzdCA8PSBMICYmIFIgPD0gZW4pCiAgICAgICAgcmV0dXJuIHRyZWVbaWRdOwogICAgaW50IG1pZCA9IChMICsgUikgPj4gMTsKICAgIFByb3BhZ2F0ZShpZCwgTCwgbWlkLCBSKTsKICAgIGlmKGVuIDw9IG1pZCkKICAgICAgICByZXR1cm4gUXVlcnkoc3QsIGVuLCBpZCA8PCAxLCBMLCBtaWQpOwogICAgaWYoc3QgPiBtaWQpCiAgICAgICAgcmV0dXJuIFF1ZXJ5KHN0LCBlbiwgaWQgPDwgMSB8IDEsIG1pZCArIDEsIFIpOwogICAgcmV0dXJuIFF1ZXJ5KHN0LCBlbiwgaWQgPDwgMSwgTCwgbWlkKSArIFF1ZXJ5KHN0LCBlbiwgaWQgPDwgMSB8IDEsIG1pZCArIDEsIFIpOwp9CgppbnQgbWFpbigpewoKICAgIHNjYW5mKCIlZCIsICZUKTsKICAgIHdoaWxlKFQtLSkgewogICAgICAgIG1lbXNldChsYXp5LCAwLCBzaXplb2YgbGF6eSk7CiAgICAgICAgbWVtc2V0KHRyZWUsIDAsIHNpemVvZiB0cmVlKTsKICAgICAgICBzY2FuZigiJWQgJWQiLCAmbiwgJnEpOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgICAgICAgICAgc2NhbmYoIiVkIiwgYXJyICsgaSk7CiAgICAgICAgQnVpbGQoKTsKICAgICAgICB3aGlsZSAocS0tKXsKICAgICAgICAgICAgaW50IHQsIEwsIFIsIHg7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCAlZCIsICZ0LCAmTCwgJlIpOwogICAgICAgICAgICBpZiAodCA9PSAxKQogICAgICAgICAgICAgICAgVXBkYXRlU3FydChMLCBSKTsKICAgICAgICAgICAgZWxzZSBpZih0ID09IDIpCiAgICAgICAgICAgICAgICBwcmludGYoIiVsbGRcbiIsIFF1ZXJ5KEwsIFIpKTsKICAgICAgICAgICAgZWxzZSBpZih0ID09IDMpewogICAgICAgICAgICAgICAgc2NhbmYoIiVkIiwgJngpOwogICAgICAgICAgICAgICAgVXBkYXRlUmFuZ2UoTCwgUiwgeCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=