#include<string.h>
#define MAX 1000000
#include<stdio.h>
struct abc
{
int zero,one,two,flip; //flip for lazy propagation; one two zero are elements leaving 1,2,0 as remainder when divided by 3
}tree[MAX];
void build(int node,int left,int right)
{
if(left==right)
{
tree[node].zero=1; //initially elements are zero,
tree[node].one=0;
tree[node].two=0;
tree[node].flip=0;
return;
}
int mid=left+right;
mid/=2;
build(2*node,left,mid);
build(2*node+1,mid+1,right);
tree[node].zero=tree[2*node].zero+tree[2*node+1].zero; //Rest are zero initially, except this field
tree[node].one=0;
tree[node].two=0;
tree[node].flip=0;
}
void update(int node,int left,int right,int i,int j)
{
if(tree[node].flip!=0) //We need to flip once, twice or zero times
{
int temp=tree[node].one;
tree[node].one=tree[node].zero;
tree[node].zero=tree[node].two;
tree[node].two=temp;
if(tree[node].flip==2) //If one flip, it is done above. For two flips, the swapping is done again
{
int temp=tree[node].one;
tree[node].one=tree[node].zero;
tree[node].zero=tree[node].two;
tree[node].two=temp;
}
if(i!=j) //Children flip count is incremented, modulo 3 to find number of swapping step required
{
tree[2*node].flip+=1;
tree[2*node+1].flip+=1;
tree[2*node].flip%=3;
tree[2*node+1].flip%=3;
}
tree[node].flip=0;
}
if(i>right || j<left) //out of bound
return;
if(i>=left && j<=right)
{
int temp=tree[node].one;
tree[node].one=tree[node].zero;
tree[node].zero=tree[node].two;
tree[node].two=temp;
if(i!=j)
{
tree[2*node].flip+=1;
tree[2*node+1].flip+=1;
tree[2*node].flip%=3;
tree[2*node+1].flip%=3;
}
return;
}
int mid=i+j;
mid/=2;
update(2*node,left,right,i,mid);
update(2*node+1,left,right,mid+1,j);
tree[node].zero=tree[2*node].zero+tree[2*node+1].zero;
tree[node].one=tree[2*node].one+tree[2*node+1].one;
tree[node].two=tree[2*node].two+tree[2*node+1].two;
}
int query(int node,int left,int right,int i,int j)
{
if(i>right || j<left)
return 0;
if(tree[node].flip!=0)
{
int temp=tree[node].one;
tree[node].one=tree[node].zero;
tree[node].zero=tree[node].two;
tree[node].two=temp;
if(tree[node].flip==2)
{
int temp=tree[node].one;
tree[node].one=tree[node].zero;
tree[node].zero=tree[node].two;
tree[node].two=temp;
}
if(i!=j)
{
tree[2*node].flip+=1;
tree[2*node+1].flip+=1;
tree[2*node].flip%=3;
tree[2*node+1].flip%=3;
}
tree[node].flip=0;
}
if(i>=left && j<=right)
return tree[node].zero;
int mid=i+j;
mid/=2;
int a=query(2*node,left,right,i,mid);
int b=query(2*node+1,left,right,mid+1,j);
return a+b;
}
int main()
{
int n,q;
build(1,0,n-1);
while(q--)
{
int a,b,c;
scanf("%d%d%d",&a
,&b
,&c
); if(a)
{
printf("%d\n",query
(1,b
,c
,0,n
-1)); }
else
{
update(1,b,c,0,n-1);
}
}
}
I2luY2x1ZGU8c3RyaW5nLmg+CiNkZWZpbmUgTUFYIDEwMDAwMDAKI2luY2x1ZGU8c3RkaW8uaD4Kc3RydWN0IGFiYwp7CglpbnQgemVybyxvbmUsdHdvLGZsaXA7CS8vZmxpcCBmb3IgbGF6eSBwcm9wYWdhdGlvbjsgb25lIHR3byB6ZXJvIGFyZSBlbGVtZW50cyBsZWF2aW5nIDEsMiwwIGFzIHJlbWFpbmRlciB3aGVuIGRpdmlkZWQgYnkgMwp9dHJlZVtNQVhdOwp2b2lkIGJ1aWxkKGludCBub2RlLGludCBsZWZ0LGludCByaWdodCkKewoJaWYobGVmdD09cmlnaHQpCgl7CgkJdHJlZVtub2RlXS56ZXJvPTE7CS8vaW5pdGlhbGx5IGVsZW1lbnRzIGFyZSB6ZXJvLCAKCQl0cmVlW25vZGVdLm9uZT0wOwoJCXRyZWVbbm9kZV0udHdvPTA7CgkJdHJlZVtub2RlXS5mbGlwPTA7CgkJcmV0dXJuOwoJfQoJaW50IG1pZD1sZWZ0K3JpZ2h0OwoJbWlkLz0yOwoJYnVpbGQoMipub2RlLGxlZnQsbWlkKTsKCWJ1aWxkKDIqbm9kZSsxLG1pZCsxLHJpZ2h0KTsKCXRyZWVbbm9kZV0uemVybz10cmVlWzIqbm9kZV0uemVybyt0cmVlWzIqbm9kZSsxXS56ZXJvOwkvL1Jlc3QgYXJlIHplcm8gaW5pdGlhbGx5LCBleGNlcHQgdGhpcyBmaWVsZAoJdHJlZVtub2RlXS5vbmU9MDsKCXRyZWVbbm9kZV0udHdvPTA7Cgl0cmVlW25vZGVdLmZsaXA9MDsKfQp2b2lkIHVwZGF0ZShpbnQgbm9kZSxpbnQgbGVmdCxpbnQgcmlnaHQsaW50IGksaW50IGopCnsKCWlmKHRyZWVbbm9kZV0uZmxpcCE9MCkJCS8vV2UgbmVlZCB0byBmbGlwIG9uY2UsIHR3aWNlIG9yIHplcm8gdGltZXMKCXsKCQlpbnQgdGVtcD10cmVlW25vZGVdLm9uZTsKCQl0cmVlW25vZGVdLm9uZT10cmVlW25vZGVdLnplcm87CgkJdHJlZVtub2RlXS56ZXJvPXRyZWVbbm9kZV0udHdvOwoJCXRyZWVbbm9kZV0udHdvPXRlbXA7CgkJCgkJaWYodHJlZVtub2RlXS5mbGlwPT0yKQkvL0lmIG9uZSBmbGlwLCBpdCBpcyBkb25lIGFib3ZlLiBGb3IgdHdvIGZsaXBzLCB0aGUgc3dhcHBpbmcgaXMgZG9uZSBhZ2FpbgoJCXsKCQkJaW50IHRlbXA9dHJlZVtub2RlXS5vbmU7CgkJCXRyZWVbbm9kZV0ub25lPXRyZWVbbm9kZV0uemVybzsKCQkJdHJlZVtub2RlXS56ZXJvPXRyZWVbbm9kZV0udHdvOwoJCQl0cmVlW25vZGVdLnR3bz10ZW1wOwoJCX0KCQlpZihpIT1qKQkJLy9DaGlsZHJlbiBmbGlwIGNvdW50IGlzIGluY3JlbWVudGVkLCBtb2R1bG8gMyB0byBmaW5kIG51bWJlciBvZiBzd2FwcGluZyBzdGVwIHJlcXVpcmVkCgkJewoJCQl0cmVlWzIqbm9kZV0uZmxpcCs9MTsKCQkJdHJlZVsyKm5vZGUrMV0uZmxpcCs9MTsKCQkJdHJlZVsyKm5vZGVdLmZsaXAlPTM7CgkJCXRyZWVbMipub2RlKzFdLmZsaXAlPTM7CgkJfQoJCXRyZWVbbm9kZV0uZmxpcD0wOwoJfQoJaWYoaT5yaWdodCB8fCBqPGxlZnQpCS8vb3V0IG9mIGJvdW5kCgkJcmV0dXJuOwoJaWYoaT49bGVmdCAmJiBqPD1yaWdodCkKCXsKCQlpbnQgdGVtcD10cmVlW25vZGVdLm9uZTsKCQl0cmVlW25vZGVdLm9uZT10cmVlW25vZGVdLnplcm87CgkJdHJlZVtub2RlXS56ZXJvPXRyZWVbbm9kZV0udHdvOwoJCXRyZWVbbm9kZV0udHdvPXRlbXA7CgkJaWYoaSE9aikKCQl7CgkJCXRyZWVbMipub2RlXS5mbGlwKz0xOwoJCQl0cmVlWzIqbm9kZSsxXS5mbGlwKz0xOwoJCQl0cmVlWzIqbm9kZV0uZmxpcCU9MzsKCQkJdHJlZVsyKm5vZGUrMV0uZmxpcCU9MzsKCQl9CgkJcmV0dXJuOwoJfQoJaW50IG1pZD1pK2o7CgltaWQvPTI7Cgl1cGRhdGUoMipub2RlLGxlZnQscmlnaHQsaSxtaWQpOwoJdXBkYXRlKDIqbm9kZSsxLGxlZnQscmlnaHQsbWlkKzEsaik7Cgl0cmVlW25vZGVdLnplcm89dHJlZVsyKm5vZGVdLnplcm8rdHJlZVsyKm5vZGUrMV0uemVybzsKCXRyZWVbbm9kZV0ub25lPXRyZWVbMipub2RlXS5vbmUrdHJlZVsyKm5vZGUrMV0ub25lOwoJdHJlZVtub2RlXS50d289dHJlZVsyKm5vZGVdLnR3byt0cmVlWzIqbm9kZSsxXS50d287Cn0KaW50IHF1ZXJ5KGludCBub2RlLGludCBsZWZ0LGludCByaWdodCxpbnQgaSxpbnQgaikKewoJaWYoaT5yaWdodCB8fCBqPGxlZnQpCgkJcmV0dXJuIDA7CglpZih0cmVlW25vZGVdLmZsaXAhPTApCgl7CgkJaW50IHRlbXA9dHJlZVtub2RlXS5vbmU7CgkJdHJlZVtub2RlXS5vbmU9dHJlZVtub2RlXS56ZXJvOwoJCXRyZWVbbm9kZV0uemVybz10cmVlW25vZGVdLnR3bzsKCQl0cmVlW25vZGVdLnR3bz10ZW1wOwoJCWlmKHRyZWVbbm9kZV0uZmxpcD09MikKCQl7CgkJCWludCB0ZW1wPXRyZWVbbm9kZV0ub25lOwoJCQl0cmVlW25vZGVdLm9uZT10cmVlW25vZGVdLnplcm87CgkJCXRyZWVbbm9kZV0uemVybz10cmVlW25vZGVdLnR3bzsKCQkJdHJlZVtub2RlXS50d289dGVtcDsKCQl9CgkJaWYoaSE9aikKCQl7CgkJCXRyZWVbMipub2RlXS5mbGlwKz0xOwoJCQl0cmVlWzIqbm9kZSsxXS5mbGlwKz0xOwoJCQl0cmVlWzIqbm9kZV0uZmxpcCU9MzsKCQkJdHJlZVsyKm5vZGUrMV0uZmxpcCU9MzsKCQl9CgkJdHJlZVtub2RlXS5mbGlwPTA7Cgl9CglpZihpPj1sZWZ0ICYmIGo8PXJpZ2h0KQoJCXJldHVybiB0cmVlW25vZGVdLnplcm87CglpbnQgbWlkPWkrajsKCW1pZC89MjsKCWludCBhPXF1ZXJ5KDIqbm9kZSxsZWZ0LHJpZ2h0LGksbWlkKTsKCWludCBiPXF1ZXJ5KDIqbm9kZSsxLGxlZnQscmlnaHQsbWlkKzEsaik7CglyZXR1cm4gYStiOwp9CmludCBtYWluKCkKewoJaW50IG4scTsKCXNjYW5mKCIlZCVkIiwmbiwmcSk7CglidWlsZCgxLDAsbi0xKTsKCXdoaWxlKHEtLSkKCXsKCQlpbnQgYSxiLGM7CgkJc2NhbmYoIiVkJWQlZCIsJmEsJmIsJmMpOwoJCWlmKGEpCgkJewoJCQlwcmludGYoIiVkXG4iLHF1ZXJ5KDEsYixjLDAsbi0xKSk7CgkJfQoJCWVsc2UKCQl7CgkJCXVwZGF0ZSgxLGIsYywwLG4tMSk7CgkJfQoJfQp9