#include <bits/stdc++.h>
using namespace std;
const int size=1<<16;
int a[size];
struct node{
int sum;
node split(node& l, node& r){};
node merge(node& l, node& r){
sum = l.sum + r.sum;
}
node setVal(int val){
sum = val;
}
};
node T[size<<1],lazy[size<<1];
void init(int Node, int i, int j){
if(i==j){
T[Node].setVal(a[i]);//for leaf nodes
return;
}
int mid = (i+j)>>1;
init(Node*2,i,mid);
init(Node*2+1,mid+1,j);
T[Node].merge(T[Node*2],T[Node*2+1]);
}
void update(int Node, int i, int j, int x,int y, int val){
if(lazy[Node].sum!=0){
// This node needs to be updated
T[Node].setVal(T[Node].sum + lazy[Node].sum); // update it
if(i!=j){
lazy[2*Node].setVal(lazy[2*Node].sum + lazy[Node].sum); // Mark child as lazy
lazy[2*Node+1].setVal(lazy[2*Node+1].sum + lazy[Node].sum); // Mark child as lazy
}
lazy[Node].sum=0; // reset
}
if(i>y||j<x || i>j) return; /// doesnot lie within the range
if(i>=x&&j<=y){ // lie within the range x,y
T[Node].setVal(T[Node].sum + val);
if(i!=j){
lazy[2*Node].setVal(lazy[2*Node].sum + val);
lazy[2*Node+1].setVal(lazy[2*Node+1].sum + val);
}
return;
}
int mid=(i+j)>>1;
update(2*Node,i,mid,x,y,val);
update(2*Node+1,mid+1,j,x,y,val);
T[Node].merge(T[2*Node],T[2*Node+1]);
}
void range_query(node& resultNode, int Node, int i, int j, int x, int y){
if(i>j || i>y || j<x) {resultNode.sum=0;return;}
if(lazy[Node].sum!=0){
// This node needs to be updated
T[Node].setVal(T[Node].sum + lazy[Node].sum); // update it
if(i!=j){
lazy[2*Node].setVal(lazy[2*Node].sum + lazy[Node].sum); // Mark child as lazy
lazy[2*Node+1].setVal(lazy[2*Node+1].sum + lazy[Node].sum); // Mark child as lazy
}
lazy[Node].sum=0; // reset
}
if(i>=x&&j<=y){
resultNode=T[Node];
return;
}
int mid=(i+j)>>1;
if(y<=mid){//if range completely lies in the left part
range_query(resultNode,Node*2,i,mid,x,y);
}
else if(x>mid){//if range completely lies in the right part
range_query(resultNode,Node*2+1,mid+1,j,x,y);
}
else{//lies partly in the range
node left, right;
range_query(left,Node*2,i,mid,x,y);
//keep the rightmost boundary fixed and find the left index
// as it lies partly in both range so mid will be same
// only we have to find the left part
range_query(right,Node*2+1,mid+1,j,x,y);
// same condition for right node mid+1 will be fixed
resultNode.merge(left,right);
}
}
int main() {
int i,n,m,x,y,t;
node res;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(i=0;i<n;i++){
a[i]=0;
}
init(1,0,n-1);
while(m--){
int op,x,y,val;
scanf("%d",&op);
if(op==1){
scanf("%d %d",&x,&y);
range_query(res,1,0,n-1,x-1,y-1);
printf("%d\n",res.sum);
}else{
scanf("%d %d %d",&x,&y,&val);
update(1, 0, n-1, x-1, y-1, val);
}
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgc2l6ZT0xPDwxNjsKaW50IGFbc2l6ZV07CgpzdHJ1Y3Qgbm9kZXsKCWludCBzdW07CgkKCW5vZGUgc3BsaXQobm9kZSYgbCwgbm9kZSYgcil7fTsKCQoJbm9kZSBtZXJnZShub2RlJiBsLCBub2RlJiByKXsKCQlzdW0gPSBsLnN1bSArIHIuc3VtOwoJfQoJCglub2RlIHNldFZhbChpbnQgdmFsKXsKCQlzdW0gPSB2YWw7Cgl9Cn07Cgpub2RlIFRbc2l6ZTw8MV0sbGF6eVtzaXplPDwxXTsKCnZvaWQgaW5pdChpbnQgTm9kZSwgaW50IGksIGludCBqKXsKCWlmKGk9PWopewoJCVRbTm9kZV0uc2V0VmFsKGFbaV0pOy8vZm9yIGxlYWYgbm9kZXMKCQlyZXR1cm47Cgl9CgkKCWludCBtaWQgPSAoaStqKT4+MTsKCQoJaW5pdChOb2RlKjIsaSxtaWQpOwoJaW5pdChOb2RlKjIrMSxtaWQrMSxqKTsKCQoJVFtOb2RlXS5tZXJnZShUW05vZGUqMl0sVFtOb2RlKjIrMV0pOwp9Cgp2b2lkIHVwZGF0ZShpbnQgTm9kZSwgaW50IGksIGludCBqLCBpbnQgeCxpbnQgeSwgaW50IHZhbCl7CgkKCWlmKGxhenlbTm9kZV0uc3VtIT0wKXsKCQkvLyBUaGlzIG5vZGUgbmVlZHMgdG8gYmUgdXBkYXRlZAoJCQoJCVRbTm9kZV0uc2V0VmFsKFRbTm9kZV0uc3VtICsgbGF6eVtOb2RlXS5zdW0pOwkJCQkvLyB1cGRhdGUgaXQKCQkKCQlpZihpIT1qKXsKCQkJbGF6eVsyKk5vZGVdLnNldFZhbChsYXp5WzIqTm9kZV0uc3VtICsgbGF6eVtOb2RlXS5zdW0pOyAJLy8gTWFyayBjaGlsZCBhcyBsYXp5CgkJCWxhenlbMipOb2RlKzFdLnNldFZhbChsYXp5WzIqTm9kZSsxXS5zdW0gKyBsYXp5W05vZGVdLnN1bSk7IC8vIE1hcmsgY2hpbGQgYXMgbGF6eQoJCX0KCQkKCQlsYXp5W05vZGVdLnN1bT0wOwkJCQkJCQkJCS8vIHJlc2V0Cgl9CgkKCWlmKGk+eXx8ajx4IHx8IGk+aikJcmV0dXJuOwkJCQkJLy8vIGRvZXNub3QgbGllIHdpdGhpbiB0aGUgcmFuZ2UKCQoJaWYoaT49eCYmajw9eSl7CQkJCQkJCQkvLyBsaWUgd2l0aGluIHRoZSByYW5nZSB4LHkKCQkKCQlUW05vZGVdLnNldFZhbChUW05vZGVdLnN1bSArIHZhbCk7CgkJCgkJaWYoaSE9ail7CgkJCWxhenlbMipOb2RlXS5zZXRWYWwobGF6eVsyKk5vZGVdLnN1bSArIHZhbCk7CgkJCWxhenlbMipOb2RlKzFdLnNldFZhbChsYXp5WzIqTm9kZSsxXS5zdW0gKyB2YWwpOwoJCX0KCQkKCQlyZXR1cm47Cgl9CgkKCQoJCglpbnQgbWlkPShpK2opPj4xOwoJCgl1cGRhdGUoMipOb2RlLGksbWlkLHgseSx2YWwpOwoJdXBkYXRlKDIqTm9kZSsxLG1pZCsxLGoseCx5LHZhbCk7CgoJVFtOb2RlXS5tZXJnZShUWzIqTm9kZV0sVFsyKk5vZGUrMV0pOwp9Cgp2b2lkIHJhbmdlX3F1ZXJ5KG5vZGUmIHJlc3VsdE5vZGUsIGludCBOb2RlLCBpbnQgaSwgaW50IGosIGludCB4LCBpbnQgeSl7CgkKCWlmKGk+aiB8fCBpPnkgfHwgajx4KSB7cmVzdWx0Tm9kZS5zdW09MDtyZXR1cm47fQoJCglpZihsYXp5W05vZGVdLnN1bSE9MCl7CgkJLy8gVGhpcyBub2RlIG5lZWRzIHRvIGJlIHVwZGF0ZWQKCQkKCQlUW05vZGVdLnNldFZhbChUW05vZGVdLnN1bSArIGxhenlbTm9kZV0uc3VtKTsJCQkJLy8gdXBkYXRlIGl0CgkJCgkJaWYoaSE9ail7CgkJCWxhenlbMipOb2RlXS5zZXRWYWwobGF6eVsyKk5vZGVdLnN1bSArIGxhenlbTm9kZV0uc3VtKTsgCS8vIE1hcmsgY2hpbGQgYXMgbGF6eQoJCQlsYXp5WzIqTm9kZSsxXS5zZXRWYWwobGF6eVsyKk5vZGUrMV0uc3VtICsgbGF6eVtOb2RlXS5zdW0pOyAvLyBNYXJrIGNoaWxkIGFzIGxhenkKCQl9CgkJCgkJbGF6eVtOb2RlXS5zdW09MDsJCQkJCQkJCQkvLyByZXNldAoJfQoJCgkKCWlmKGk+PXgmJmo8PXkpewoJCXJlc3VsdE5vZGU9VFtOb2RlXTsKCQlyZXR1cm47Cgl9CgkKCWludCBtaWQ9KGkraik+PjE7CgkKCWlmKHk8PW1pZCl7Ly9pZiByYW5nZSBjb21wbGV0ZWx5IGxpZXMgaW4gdGhlIGxlZnQgcGFydAoJCXJhbmdlX3F1ZXJ5KHJlc3VsdE5vZGUsTm9kZSoyLGksbWlkLHgseSk7Cgl9CgllbHNlIGlmKHg+bWlkKXsvL2lmIHJhbmdlIGNvbXBsZXRlbHkgbGllcyBpbiB0aGUgcmlnaHQgcGFydAoJCXJhbmdlX3F1ZXJ5KHJlc3VsdE5vZGUsTm9kZSoyKzEsbWlkKzEsaix4LHkpOwoJfQoJZWxzZXsvL2xpZXMgcGFydGx5IGluIHRoZSByYW5nZQoJCW5vZGUgbGVmdCwgcmlnaHQ7CgkJcmFuZ2VfcXVlcnkobGVmdCxOb2RlKjIsaSxtaWQseCx5KTsKCQkvL2tlZXAgdGhlIHJpZ2h0bW9zdCBib3VuZGFyeSBmaXhlZCBhbmQgZmluZCB0aGUgbGVmdCBpbmRleAoJCS8vIGFzIGl0IGxpZXMgcGFydGx5IGluIGJvdGggcmFuZ2Ugc28gbWlkIHdpbGwgYmUgc2FtZSAKCQkvLyBvbmx5IHdlIGhhdmUgdG8gZmluZCB0aGUgbGVmdCBwYXJ0CgkJcmFuZ2VfcXVlcnkocmlnaHQsTm9kZSoyKzEsbWlkKzEsaix4LHkpOwoJCS8vIHNhbWUgY29uZGl0aW9uIGZvciByaWdodCBub2RlIG1pZCsxIHdpbGwgYmUgZml4ZWQKCQkKCQlyZXN1bHROb2RlLm1lcmdlKGxlZnQscmlnaHQpOwoJfQp9CgoKCmludCBtYWluKCkgewoJaW50IGksbixtLHgseSx0OwoJbm9kZSByZXM7CglzY2FuZigiJWQiLCZ0KTsKCQoJd2hpbGUodC0tKXsKCQlzY2FuZigiJWQgJWQiLCZuLCZtKTsKCQkKCQlmb3IoaT0wO2k8bjtpKyspewoJCQlhW2ldPTA7CgkJfQoJCgkJaW5pdCgxLDAsbi0xKTsKCQkKCQl3aGlsZShtLS0pewoJCQkKCQkJaW50IG9wLHgseSx2YWw7CgkJCXNjYW5mKCIlZCIsJm9wKTsKCQkJCgkJCWlmKG9wPT0xKXsKCQkJCXNjYW5mKCIlZCAlZCIsJngsJnkpOwoJCQkJcmFuZ2VfcXVlcnkocmVzLDEsMCxuLTEseC0xLHktMSk7CgkJCQlwcmludGYoIiVkXG4iLHJlcy5zdW0pOwoJCQl9ZWxzZXsKCQkJCXNjYW5mKCIlZCAlZCAlZCIsJngsJnksJnZhbCk7CgkJCQl1cGRhdGUoMSwgMCwgbi0xLCB4LTEsIHktMSwgdmFsKTsKCQkJfQoJCX0KCX0JCgkKCXJldHVybiAwOwp9