problem

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N];
int L[N],R[N],pos[N],tag[N];
int cnt[N][3];
void rebuild(int x)
{
    for(int i=L[x];i<=R[x];++i)
        cnt[x][0]=cnt[x][1]=cnt[x][2]=0;
    for(int i=L[x];i<=R[x];++i)
        ++cnt[x][a[i]];
}
void pushdown(int x)
{
    for(int i=L[x];i<=R[x];++i)
        (a[i]+=tag[x])%=3;
    tag[x]=0;
}
void update(int l,int r)
{
    int x=pos[l],y=pos[r];
    if(x==y)
    {
        pushdown(x);
        for(int i=l;i<=r;++i)
            a[i]=(a[i]+1)%3;
        rebuild(x);
        return ;
    }
    update(l,R[x]);
    update(L[y],r);
    for(int i=x+1;i<y;++i)
    {
        int tmp=cnt[i][2];
        tag[i]=(tag[i]+1)%3;
        cnt[i][1]=cnt[i][0];
        cnt[i][2]=cnt[i][1];
        cnt[i][0]=tmp;
    }
}
int query(int l,int r)
{
    int x=pos[l],y=pos[r],ans=0;
    if(x==y)
    {
        pushdown(x);
        rebuild(x);
        for(int i=l;i<=r;++i)
            ans+=(a[i]==0);
        return ans;
    }
    for(int i=x+1;i<y;++i)
        ans+=cnt[i][0];
    return ans+query(l,R[x])+query(L[y],r);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int t=sqrt(n);
    for(int i=1;i<=t;++i)
        L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]<n)
    {
        ++t;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;++i)
    {
        for(int j=L[i];j<=R[i];++j)
            pos[j]=i;
        rebuild(i);
    }
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        ++x,++y;
        if(op==0)
            update(x,y);
        else
            cout<<query(x,y)<<'\n';
    }
}