//============================================================================
// Name : SPOJ Multiple by 3 (Segment Tree)
// Author : Tarango Khan
// Copyright : Team Byteheads
// Description : !!!Hello World!!!
//============================================================================
#include <bits/stdc++.h>
using namespace std;
#define Size 100005
struct vert{
int cnt[3];
int prop;
};
vert tree[Size*4];
void build_tree(int cur,int Start,int End){
if(Start == End){
tree[cur].cnt[0] = 1;
tree[cur].cnt[1] = 0;
tree[cur].cnt[2] = 0;
tree[cur].prop = 0;
return;
}
int left = cur*2;
int right = left+1;
int mid = (Start+End)/2;
build_tree(left,Start,mid);
build_tree(right,mid+1,End);
tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
tree[cur].prop = tree[left].prop + tree[right].prop;
}
void update_prop(int cur){
int tmp = tree[cur].cnt[2];
tree[cur].cnt[2] = tree[cur].cnt[1];
tree[cur].cnt[1] = tree[cur].cnt[0];
tree[cur].cnt[0] = tmp;
}
void update_child(int cur,int left,int right){
tree[left].prop += tree[cur].prop;
tree[right].prop += tree[cur].prop;
int rotate = tree[cur].prop%3;
for(int s = 0;s<rotate;s++){
update_prop(left);
update_prop(right);
}
tree[cur].prop = 0;
}
void update_tree(int cur,int Start,int End,int u,int v){
if(Start == u && End == v){
tree[cur].prop += 1;
update_prop(cur);
return;
}
int left = cur*2;
int right = left+1;
int mid = (Start+End)/2;
if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
update_child(cur,left,right);
}
if(v <= mid){
update_tree(left,Start,mid,u,v);
}else if(u > mid){
update_tree(right,mid+1,End,u,v);
}else{
update_tree(left,Start,mid,u,mid);
update_tree(right,mid+1,End,mid+1,v);
}
tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
}
int tree_query(int cur,int Start,int End,int u,int v){
if(Start == u && End == v){
return tree[cur].cnt[0];
}
int left = cur*2;
int right = left+1;
int mid = (Start+End)/2;
if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
update_child(cur,left,right);
}
if(v <= mid){
return tree_query(left,Start,mid,u,v);
}else if(u > mid){
return tree_query(right,mid+1,End,u,v);
}else{
return tree_query(left,Start,mid,u,mid) + tree_query(right,mid+1,End,mid+1,v);
}
}
int main() {
int N,Q,u,v,type;
scanf("%d %d",&N,&Q);
build_tree(1,1,N);
for(int i = 1;i<=Q;i++){
scanf("%d",&type);
if(type == 0){
scanf("%d %d",&u,&v);
u++;v++;
update_tree(1,1,N,u,v);
}else{
scanf("%d %d",&u,&v);
u++;v++;
int sum = tree_query(1,1,N,u,v);
printf("%d\n",sum);
}
}
return 0;
}
Ly89PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIE5hbWUgICAgICAgIDogU1BPSiBNdWx0aXBsZSBieSAzIChTZWdtZW50IFRyZWUpCi8vIEF1dGhvciAgICAgIDogVGFyYW5nbyBLaGFuCi8vIENvcHlyaWdodCAgIDogVGVhbSBCeXRlaGVhZHMKLy8gRGVzY3JpcHRpb24gOiAhISFIZWxsbyBXb3JsZCEhIQovLz09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIFNpemUgMTAwMDA1CgpzdHJ1Y3QgdmVydHsKICAgIGludCBjbnRbM107CiAgICBpbnQgcHJvcDsKfTsKdmVydCB0cmVlW1NpemUqNF07Cgp2b2lkIGJ1aWxkX3RyZWUoaW50IGN1cixpbnQgU3RhcnQsaW50IEVuZCl7CiAgICBpZihTdGFydCA9PSBFbmQpewogICAgICAgIHRyZWVbY3VyXS5jbnRbMF0gPSAxOwogICAgICAgIHRyZWVbY3VyXS5jbnRbMV0gPSAwOwogICAgICAgIHRyZWVbY3VyXS5jbnRbMl0gPSAwOwogICAgICAgIHRyZWVbY3VyXS5wcm9wID0gMDsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbGVmdCA9IGN1cioyOwogICAgaW50IHJpZ2h0ID0gbGVmdCsxOwogICAgaW50IG1pZCA9IChTdGFydCtFbmQpLzI7CiAgICBidWlsZF90cmVlKGxlZnQsU3RhcnQsbWlkKTsKICAgIGJ1aWxkX3RyZWUocmlnaHQsbWlkKzEsRW5kKTsKICAgIHRyZWVbY3VyXS5jbnRbMF0gPSB0cmVlW2xlZnRdLmNudFswXSArIHRyZWVbcmlnaHRdLmNudFswXTsKICAgIHRyZWVbY3VyXS5jbnRbMV0gPSB0cmVlW2xlZnRdLmNudFsxXSArIHRyZWVbcmlnaHRdLmNudFsxXTsKCXRyZWVbY3VyXS5jbnRbMl0gPSB0cmVlW2xlZnRdLmNudFsyXSArIHRyZWVbcmlnaHRdLmNudFsyXTsKCXRyZWVbY3VyXS5wcm9wID0gdHJlZVtsZWZ0XS5wcm9wICsgdHJlZVtyaWdodF0ucHJvcDsKfQoKdm9pZCB1cGRhdGVfcHJvcChpbnQgY3VyKXsKCWludCB0bXAgPSB0cmVlW2N1cl0uY250WzJdOwoJdHJlZVtjdXJdLmNudFsyXSA9IHRyZWVbY3VyXS5jbnRbMV07Cgl0cmVlW2N1cl0uY250WzFdID0gdHJlZVtjdXJdLmNudFswXTsKCXRyZWVbY3VyXS5jbnRbMF0gPSB0bXA7Cn0KCnZvaWQgdXBkYXRlX2NoaWxkKGludCBjdXIsaW50IGxlZnQsaW50IHJpZ2h0KXsKCXRyZWVbbGVmdF0ucHJvcCArPSB0cmVlW2N1cl0ucHJvcDsKCXRyZWVbcmlnaHRdLnByb3AgKz0gdHJlZVtjdXJdLnByb3A7CglpbnQgcm90YXRlICA9IHRyZWVbY3VyXS5wcm9wJTM7Cglmb3IoaW50IHMgPSAwO3M8cm90YXRlO3MrKyl7CgkJdXBkYXRlX3Byb3AobGVmdCk7CgkJdXBkYXRlX3Byb3AocmlnaHQpOwoJfQoJdHJlZVtjdXJdLnByb3AgPSAwOwp9Cgp2b2lkIHVwZGF0ZV90cmVlKGludCBjdXIsaW50IFN0YXJ0LGludCBFbmQsaW50IHUsaW50IHYpewogICAgaWYoU3RhcnQgPT0gdSAmJiBFbmQgPT0gdil7CiAgICAJdHJlZVtjdXJdLnByb3AgKz0gMTsKICAgIAl1cGRhdGVfcHJvcChjdXIpOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBsZWZ0ID0gY3VyKjI7CiAgICBpbnQgcmlnaHQgPSBsZWZ0KzE7CiAgICBpbnQgbWlkID0gKFN0YXJ0K0VuZCkvMjsKCiAgICBpZih0cmVlW2N1cl0ucHJvcCAhPSAwKXsgLy9JZiBwcm9wIGV4aXN0IHRoZW4gd2UgYWRkIHRoYXQgdG8gaGlzIGNoaWxkIGFuZCBtYWtlIGhpcyBvbmUgdG8gMDsKCQl1cGRhdGVfY2hpbGQoY3VyLGxlZnQscmlnaHQpOwoJfQoKICAgIGlmKHYgPD0gbWlkKXsKICAgIAl1cGRhdGVfdHJlZShsZWZ0LFN0YXJ0LG1pZCx1LHYpOwogICAgfWVsc2UgaWYodSA+IG1pZCl7CiAgICAJdXBkYXRlX3RyZWUocmlnaHQsbWlkKzEsRW5kLHUsdik7CiAgICB9ZWxzZXsKICAgIAl1cGRhdGVfdHJlZShsZWZ0LFN0YXJ0LG1pZCx1LG1pZCk7CiAgICAJdXBkYXRlX3RyZWUocmlnaHQsbWlkKzEsRW5kLG1pZCsxLHYpOwogICAgfQogICAgdHJlZVtjdXJdLmNudFswXSA9IHRyZWVbbGVmdF0uY250WzBdICsgdHJlZVtyaWdodF0uY250WzBdOwogICAgdHJlZVtjdXJdLmNudFsxXSA9IHRyZWVbbGVmdF0uY250WzFdICsgdHJlZVtyaWdodF0uY250WzFdOwogICAgdHJlZVtjdXJdLmNudFsyXSA9IHRyZWVbbGVmdF0uY250WzJdICsgdHJlZVtyaWdodF0uY250WzJdOwp9CgppbnQgdHJlZV9xdWVyeShpbnQgY3VyLGludCBTdGFydCxpbnQgRW5kLGludCB1LGludCB2KXsKICAgIGlmKFN0YXJ0ID09IHUgJiYgRW5kID09IHYpewogICAgCXJldHVybiB0cmVlW2N1cl0uY250WzBdOwogICAgfQogICAgaW50IGxlZnQgPSBjdXIqMjsKICAgIGludCByaWdodCA9IGxlZnQrMTsKICAgIGludCBtaWQgPSAoU3RhcnQrRW5kKS8yOwogICAgaWYodHJlZVtjdXJdLnByb3AgIT0gMCl7IC8vSWYgcHJvcCBleGlzdCB0aGVuIHdlIGFkZCB0aGF0IHRvIGhpcyBjaGlsZCBhbmQgbWFrZSBoaXMgb25lIHRvIDA7CiAgICAJdXBkYXRlX2NoaWxkKGN1cixsZWZ0LHJpZ2h0KTsKCX0KICAgIGlmKHYgPD0gbWlkKXsKCQlyZXR1cm4gdHJlZV9xdWVyeShsZWZ0LFN0YXJ0LG1pZCx1LHYpOwoJfWVsc2UgaWYodSA+IG1pZCl7CgkJcmV0dXJuIHRyZWVfcXVlcnkocmlnaHQsbWlkKzEsRW5kLHUsdik7Cgl9ZWxzZXsKCQlyZXR1cm4gdHJlZV9xdWVyeShsZWZ0LFN0YXJ0LG1pZCx1LG1pZCkgKyB0cmVlX3F1ZXJ5KHJpZ2h0LG1pZCsxLEVuZCxtaWQrMSx2KTsKCX0KfQoKaW50IG1haW4oKSB7CiAgICBpbnQgTixRLHUsdix0eXBlOwoJc2NhbmYoIiVkICVkIiwmTiwmUSk7CglidWlsZF90cmVlKDEsMSxOKTsKCWZvcihpbnQgaSA9IDE7aTw9UTtpKyspewoJCXNjYW5mKCIlZCIsJnR5cGUpOwoJCWlmKHR5cGUgPT0gMCl7CgkJCXNjYW5mKCIlZCAlZCIsJnUsJnYpOwoJCQl1Kys7disrOwoJCQl1cGRhdGVfdHJlZSgxLDEsTix1LHYpOwoJCX1lbHNlewoJCQlzY2FuZigiJWQgJWQiLCZ1LCZ2KTsKCQkJdSsrO3YrKzsKCQkJaW50IHN1bSA9IHRyZWVfcXVlcnkoMSwxLE4sdSx2KTsKCQkJcHJpbnRmKCIlZFxuIixzdW0pOwoJCX0KCX0KICAgIHJldHVybiAwOwp9Cg==