#include <iostream>
#include<stdio.h>
using namespace std;
#define max 100001
int tree[4*max], a[max],val=1,lazy[max];
int __ch,__sign,h;
inline void S( int &x )
{
x=0;
while((__ch<'0' || __ch>'9') && __ch!='-' && __ch!=EOF) __ch=getchar_unlocked();
if (__ch=='-')
__sign=-1 , __ch=getchar_unlocked();
else
__sign=1;
do
x=(x<<3)+(x<<1)+__ch-'0';
while((__ch=getchar_unlocked())>='0' && __ch<='9');
x*=__sign;
}
void build_tree(int node, int a[], int start, int end)
{
if(start==end)
{
tree[node] = (a[start]%3==0?1:0);
//cout<<" node is "<<node<<" : "<<tree[node]<<endl;
}
else
{
int mid = (start+end)/2;
build_tree(1+(2*node),a,start, mid);
build_tree(2+(2*node), a, mid+1, end);
tree[node] = tree[1+ 2*node] + tree[2+ 2*node];
}
}
int get_mul(int node, int start, int end, int l , int r)
{
if(start>=l && end<=r)
return tree[node];
if(l>end || start>r)
return 0;
int mid= (start+end)/2;
int p1= get_mul(1+ 2*node, start, mid, l,r);
int p2= get_mul(2+ 2*node, mid+1, end, l,r);
return p1+p2;
}
void update(int node, int start, int end, int l, int r)
{
/*
if(lazy[node]!=0)
{
tree[node]+=lazy[node];
if(start!=end)
{
lazy[1+ 2*node]+=lazy[node];
lazy[2+ 2*node]+=lazy[node];
}
lazy[node]=0;
}
*/
if(l>end || start>r)
return;
if(start==end)
{
a[start]++;
if(a[start]%3==0)
tree[node]=1;
else tree[node]=0;
return;
}
int mid= (start+end)/2;
update(1+ 2*node, start, mid, l,r);
update(2+ 2*node, mid+1, end, l,r);
tree[node] = tree[1+ 2*node] + tree[2+ 2*node];
}
int main() {
// your code goes here
int n,f,x,y,i,q;
//cin>>n>>q;
S(n); S(q);
build_tree(0,a,0,n-1);
/*
cout<<"The tree build is \n";
for(i=0;i<13;i++)
cout<<" i- "<<i<<": "<<tree[i]<<" \n";
*/
while(q--)
{
//cin>>f>>x>>y;
S(f); S(x); S(y);
if(f==1)
cout<<get_mul(0,0,n-1,x,y)<<endl;
else
{
update(0,0,n-1,x,y);
/*cout<<"the tree is \n";
for(i=0;i<13;i++)
cout<<tree[i]<<" ";
cout<<endl;*/
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTxzdGRpby5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBtYXggMTAwMDAxCgppbnQgdHJlZVs0Km1heF0sIGFbbWF4XSx2YWw9MSxsYXp5W21heF07CgppbnQgX19jaCxfX3NpZ24saDsKIAppbmxpbmUgdm9pZCBTKCAgaW50ICZ4ICkKewoJeD0wOwoJd2hpbGUoKF9fY2g8JzAnIHx8IF9fY2g+JzknKSAmJiBfX2NoIT0nLScgJiYgX19jaCE9RU9GKQlfX2NoPWdldGNoYXJfdW5sb2NrZWQoKTsKCWlmIChfX2NoPT0nLScpCgkJX19zaWduPS0xICwgX19jaD1nZXRjaGFyX3VubG9ja2VkKCk7CgllbHNlCgkJX19zaWduPTE7CgkKCWRvCgkJeD0oeDw8MykrKHg8PDEpK19fY2gtJzAnOwoJd2hpbGUoKF9fY2g9Z2V0Y2hhcl91bmxvY2tlZCgpKT49JzAnICYmIF9fY2g8PSc5Jyk7Cgl4Kj1fX3NpZ247Cn0KCnZvaWQgYnVpbGRfdHJlZShpbnQgbm9kZSwgaW50IGFbXSwgaW50IHN0YXJ0LCBpbnQgZW5kKQp7CglpZihzdGFydD09ZW5kKQoJIHsKCSAJdHJlZVtub2RlXSA9IChhW3N0YXJ0XSUzPT0wPzE6MCk7CgkgCS8vY291dDw8IiBub2RlIGlzICI8PG5vZGU8PCIgOiAiPDx0cmVlW25vZGVdPDxlbmRsOwoJIH0KCWVsc2UKCXsKCQlpbnQgbWlkID0gKHN0YXJ0K2VuZCkvMjsKCQlidWlsZF90cmVlKDErKDIqbm9kZSksYSxzdGFydCwgbWlkKTsKCQlidWlsZF90cmVlKDIrKDIqbm9kZSksIGEsIG1pZCsxLCBlbmQpOwoJCXRyZWVbbm9kZV0gPSB0cmVlWzErIDIqbm9kZV0gKyB0cmVlWzIrIDIqbm9kZV07Cgl9Cn0KCmludCBnZXRfbXVsKGludCBub2RlLCBpbnQgc3RhcnQsIGludCBlbmQsIGludCBsICwgaW50IHIpCnsKCWlmKHN0YXJ0Pj1sICYmIGVuZDw9cikKCSByZXR1cm4gdHJlZVtub2RlXTsKCQoJaWYobD5lbmQgfHwgc3RhcnQ+cikKCSByZXR1cm4gMDsKCSAKCWludCBtaWQ9IChzdGFydCtlbmQpLzI7CgkKCWludCBwMT0gZ2V0X211bCgxKyAyKm5vZGUsIHN0YXJ0LCBtaWQsIGwscik7CglpbnQgcDI9IGdldF9tdWwoMisgMipub2RlLCBtaWQrMSwgZW5kLCBsLHIpOwoJcmV0dXJuIHAxK3AyOwp9Cgp2b2lkIHVwZGF0ZShpbnQgbm9kZSwgaW50IHN0YXJ0LCBpbnQgZW5kLCBpbnQgbCwgaW50IHIpCnsKCS8qCglpZihsYXp5W25vZGVdIT0wKQoJewoJCXRyZWVbbm9kZV0rPWxhenlbbm9kZV07CgkJaWYoc3RhcnQhPWVuZCkKCQl7CgkJCWxhenlbMSsgMipub2RlXSs9bGF6eVtub2RlXTsKCQkJbGF6eVsyKyAyKm5vZGVdKz1sYXp5W25vZGVdOwoJCX0KCQlsYXp5W25vZGVdPTA7Cgl9CgkqLwoJaWYobD5lbmQgfHwgc3RhcnQ+cikKCSByZXR1cm47CgkKCWlmKHN0YXJ0PT1lbmQpCgl7CgkJYVtzdGFydF0rKzsKCQlpZihhW3N0YXJ0XSUzPT0wKQoJCSB0cmVlW25vZGVdPTE7CgkJZWxzZSB0cmVlW25vZGVdPTA7CgkJCgkJcmV0dXJuOwoJfQoJCglpbnQgbWlkPSAoc3RhcnQrZW5kKS8yOwoJCgkgdXBkYXRlKDErIDIqbm9kZSwgc3RhcnQsIG1pZCwgbCxyKTsKCSB1cGRhdGUoMisgMipub2RlLCBtaWQrMSwgZW5kLCBsLHIpOwogICAgIHRyZWVbbm9kZV0gPSB0cmVlWzErIDIqbm9kZV0gKyB0cmVlWzIrIDIqbm9kZV07CgkKfQoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgbixmLHgseSxpLHE7CgkvL2Npbj4+bj4+cTsKCVMobik7IFMocSk7CglidWlsZF90cmVlKDAsYSwwLG4tMSk7CgkvKgoJY291dDw8IlRoZSB0cmVlIGJ1aWxkIGlzIFxuIjsKCQoJZm9yKGk9MDtpPDEzO2krKykKCSBjb3V0PDwiIGktICI8PGk8PCI6ICI8PHRyZWVbaV08PCIgXG4iOwoJCgkqLwoJCgl3aGlsZShxLS0pCgl7CgkJLy9jaW4+PmY+Png+Pnk7CgkJUyhmKTsgUyh4KTsgUyh5KTsKCQlpZihmPT0xKQoJCWNvdXQ8PGdldF9tdWwoMCwwLG4tMSx4LHkpPDxlbmRsOwoJCWVsc2UKCQl7CgkJCXVwZGF0ZSgwLDAsbi0xLHgseSk7CgkJCS8qY291dDw8InRoZSB0cmVlIGlzIFxuIjsKCQkJZm9yKGk9MDtpPDEzO2krKykKCQkJIGNvdXQ8PHRyZWVbaV08PCIgIjsKCQkJIAoJCQkgY291dDw8ZW5kbDsqLwoJCX0KCX0KCQoJcmV0dXJuIDA7Cn0=