#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long int segtree[4100000];
long long int lazy[4100000];
void updatetree(int low,int high,int value,int qlow,int qhigh,int pos);
long long int addtree(int low,int high,int qlow,int qhigh,int pos);
int main()
{
ios::sync_with_stdio(false);
int t,b;
long long int n,c,p,q,v,i;
cin>>t;
while(t--)
{
cin>>n>>c;
for(i=0;i<450000;i++)
{
lazy[i]=0;
segtree[i]=0;
}
for(i=0;i<c;i++)
{
cin>>b;
if(b==0)
{
cin>>p>>q>>v;
updatetree(0,n-1,v,p-1,q-1,0);
}
else
{
cin>>p>>q;
cout<<addtree(0,n-1,p-1,q-1,0)<<"\n";
}
}
}
return 0;
}
void updatetree(int low,int high,int value,int qlow,int qhigh,int pos)
{
if(high < qlow||low>high||qhigh<low)
return;
if(lazy[pos]!=0) //upadate query should contain the low & mid ranges
{
segtree[pos]+=lazy[pos];
if(low!=high) //verify the proof
{
lazy[2*pos+1]+=lazy[pos];
lazy[2*pos+2]+=lazy[pos];
}
lazy[pos]=0;
}
if(qlow<=low&&qhigh>=high)
{
segtree[pos]+=value;
if(low!=high)
{
lazy[2*pos+1]+=value;
lazy[2*pos+2]+=value;
}
return ;
}
//if partial overlaps
long long int mid;
mid=(low+high)/2;
updatetree(low,mid,value,qlow,qhigh,2*pos+1);
updatetree(mid+1,high,value,qlow,qhigh,2+pos+2);
segtree[pos]=min(segtree[2*pos+1],segtree[2*pos+2]);
}
long long int addtree(int low,int high,int qlow,int qhigh,int pos)
{
if(qlow>high||qhigh<low||high<low||qhigh<qlow)
return 0;
if(lazy[pos]!=0)
{
segtree[pos]+=lazy[pos];
if(low!=high)
{
lazy[2*pos+1]+=lazy[pos];
lazy[2*pos+2]+=lazy[pos];
}
lazy[pos]=0;
}
if(qlow<=low&&qhigh>=high)
{
return segtree[pos];
}
long long int mid=(low+high)/2;
long long int q,y;
q=addtree(low,mid,qlow,qhigh,2*pos+1);
y=addtree(mid+1,high,qlow,qhigh,2*pos+2);
return q+y;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpsb25nIGxvbmcgaW50IHNlZ3RyZWVbNDEwMDAwMF07CmxvbmcgbG9uZyBpbnQgbGF6eVs0MTAwMDAwXTsKdm9pZCB1cGRhdGV0cmVlKGludCBsb3csaW50IGhpZ2gsaW50IHZhbHVlLGludCBxbG93LGludCBxaGlnaCxpbnQgcG9zKTsKbG9uZyBsb25nIGludCBhZGR0cmVlKGludCBsb3csaW50IGhpZ2gsaW50IHFsb3csaW50IHFoaWdoLGludCBwb3MpOwppbnQgbWFpbigpCiAgIHsKICAgICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgICAgIGludCB0LGI7CiAgICAgICBsb25nIGxvbmcgaW50ICBuLGMscCxxLHYsaTsKICAgICAgIGNpbj4+dDsKICAgICAgIHdoaWxlKHQtLSkKICAgICAgIHsKICAgICAgICAgICBjaW4+Pm4+PmM7CiAgICAgICAgICAgZm9yKGk9MDtpPDQ1MDAwMDtpKyspCiAgICAgICAgICAgewogICAgICAgICAgICAgICBsYXp5W2ldPTA7CiAgICAgICAgICAgICAgIHNlZ3RyZWVbaV09MDsKICAgICAgICAgICB9CiAgICAKICAgICAgICAgICBmb3IoaT0wO2k8YztpKyspCiAgICAgICAgICAgewogICAgICAgICAgICBjaW4+PmI7CiAgICAgICAgICAgIGlmKGI9PTApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNpbj4+cD4+cT4+djsKICAgICAgICAgICAgICAgdXBkYXRldHJlZSgwLG4tMSx2LHAtMSxxLTEsMCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNpbj4+cD4+cTsKCiAgICAgICAgICAgICAgICBjb3V0PDxhZGR0cmVlKDAsbi0xLHAtMSxxLTEsMCk8PCJcbiI7CiAgICAgICAgICAgIH0KICAgICAgICAgICB9CiAgICAgICB9CiAgICAgICByZXR1cm4gMDsKICAgfQoKCnZvaWQgdXBkYXRldHJlZShpbnQgbG93LGludCBoaWdoLGludCB2YWx1ZSxpbnQgcWxvdyxpbnQgcWhpZ2gsaW50IHBvcykKICAgewogICAgICAgaWYoaGlnaCA8IHFsb3d8fGxvdz5oaWdofHxxaGlnaDxsb3cpCiAgICAgICAgcmV0dXJuOwogICAgICAgaWYobGF6eVtwb3NdIT0wKSAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vdXBhZGF0ZSBxdWVyeSBzaG91bGQgY29udGFpbiB0aGUgbG93ICYgbWlkIHJhbmdlcwogICAgICAgIHsKICAgICAgICAgICAgc2VndHJlZVtwb3NdKz1sYXp5W3Bvc107CiAgICAgICAgICAgIGlmKGxvdyE9aGlnaCkgICAgICAgICAgICAgICAgICAgICAgICAvL3ZlcmlmeSB0aGUgcHJvb2YKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgbGF6eVsyKnBvcysxXSs9bGF6eVtwb3NdOwogICAgICAgICAgICAgIGxhenlbMipwb3MrMl0rPWxhenlbcG9zXTsKICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgbGF6eVtwb3NdPTA7CiAgICAgICAgfQoKICAgICAgICBpZihxbG93PD1sb3cmJnFoaWdoPj1oaWdoKQogICAgICAgIHsKICAgICAgICAgICAgc2VndHJlZVtwb3NdKz12YWx1ZTsKICAgICAgICAgICAgaWYobG93IT1oaWdoKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsYXp5WzIqcG9zKzFdKz12YWx1ZTsKICAgICAgICAgICAgICAgIGxhenlbMipwb3MrMl0rPXZhbHVlOwogICAgICAgICAgICB9CiAgICAgICAgICByZXR1cm4gOwogICAgICAgIH0KICAgICAgICAvL2lmIHBhcnRpYWwgb3ZlcmxhcHMKICAgICAgICBsb25nIGxvbmcgaW50IG1pZDsKICAgICAgICBtaWQ9KGxvdytoaWdoKS8yOwogICAgICAgIHVwZGF0ZXRyZWUobG93LG1pZCx2YWx1ZSxxbG93LHFoaWdoLDIqcG9zKzEpOwogICAgICAgIHVwZGF0ZXRyZWUobWlkKzEsaGlnaCx2YWx1ZSxxbG93LHFoaWdoLDIrcG9zKzIpOwogICAgICAgIHNlZ3RyZWVbcG9zXT1taW4oc2VndHJlZVsyKnBvcysxXSxzZWd0cmVlWzIqcG9zKzJdKTsKICAgfQoKbG9uZyBsb25nIGludCBhZGR0cmVlKGludCBsb3csaW50IGhpZ2gsaW50IHFsb3csaW50IHFoaWdoLGludCBwb3MpCiAgICAgIHsKICAgICAgaWYocWxvdz5oaWdofHxxaGlnaDxsb3d8fGhpZ2g8bG93fHxxaGlnaDxxbG93KQogICAgICByZXR1cm4gMDsKCiAgICAgIGlmKGxhenlbcG9zXSE9MCkKICAgICAgICB7CiAgICAgICAgc2VndHJlZVtwb3NdKz1sYXp5W3Bvc107CiAgICAgICAgaWYobG93IT1oaWdoKQogICAgICAgICB7CiAgICAgICAgICBsYXp5WzIqcG9zKzFdKz1sYXp5W3Bvc107CiAgICAgICAgICBsYXp5WzIqcG9zKzJdKz1sYXp5W3Bvc107CiAgICAgICAgIH0KICAgICAgICAgbGF6eVtwb3NdPTA7CiAgICAgICAgfQoKICAgICBpZihxbG93PD1sb3cmJnFoaWdoPj1oaWdoKQogICAgIHsKICAgICAgICAgcmV0dXJuIHNlZ3RyZWVbcG9zXTsKICAgICB9CgogICAgbG9uZyBsb25nIGludCBtaWQ9KGxvdytoaWdoKS8yOwogICAgbG9uZyBsb25nIGludCBxLHk7CiAgICBxPWFkZHRyZWUobG93LG1pZCxxbG93LHFoaWdoLDIqcG9zKzEpOwogICAgeT1hZGR0cmVlKG1pZCsxLGhpZ2gscWxvdyxxaGlnaCwyKnBvcysyKTsKICAgIHJldHVybiBxK3k7CiAgICAgIH0K