题解：

• 分块对每个块的起点$st[i]$到$n$做一次回文自动机;
• 由于子串的回文自动机是原串的子图，所以并不需要重新构图，在原来的图上做即可；
• 做的时候记录某个终点的本质不同的回文串和$sum[i][r]$
• 对于询问$[l,r]$，直接统计$l$后的整块，考虑统计$l$所在的散块$[l,st[i]]$
• 根据回文串的对称性，可以预处理出在$st[i]$匹配的最长回文后缀节点，所以从st[i]到l暴力即可；
• 注意判断是否重复和是否超出边界；
• 暂时还不会两个log的做法；

•  #include<bits/stdc++.h>
  
   #define rg register
  
   using namespace std;
  
   const int M=,N=;
  
   int T,n,m,typ,sz,ch[N][],Fl[N][],fl[N],end[M][N],pos[M][N];
  
   int sum[M][N],u,tot,bl[N],st[N],ed[N],lst,vis[N],len[N],s[N];
  
   inline char gc(){
  
       static char*p1,*p2,buf[];
  
       if(p1==p2)p2=(p1=buf)+fread(buf,,,stdin);
  
       return(p1==p2)?EOF:*p1++;
  
   }
  
   inline int rd(){
  
       int x=;char c=gc();
  
       while(c<''||c>'')c=gc();
  
       while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
  
       return x;
  
   }
  
   void extend1(int l,int i){
  
       int x=lst;
  
       if(i-len[x]-<l||s[i-len[x]-]!=s[i])x=Fl[x][s[i]];
  
       if(!ch[x][s[i]]){
  
           len[++sz]=len[x]+;
  
           int y=fl[x];
  
           if(s[i-len[y]-]!=s[i])y=Fl[y][s[i]];y=ch[y][s[i]];
  
           memcpy(Fl[sz],Fl[y],sizeof(Fl[y]));
  
           Fl[sz][s[i-len[y]]]=fl[sz]=y;
  
           ch[x][s[i]]=sz;
  
       }
  
       lst=x=ch[x][s[i]];
  
   }
  
   void extend2(int i,int r){
  
       int x=lst;
  
       if(i+len[x]+>r||s[i+len[x]+]!=s[i])x=Fl[x][s[i]];
  
       if(!ch[x][s[i]]){
  
           len[++sz]=len[x]+;
  
           int y=fl[x];
  
           if(s[i+len[y]+]!=s[i])y=Fl[y][s[i]];y=ch[y][s[i]];
  
           memcpy(Fl[sz],Fl[y],sizeof(Fl[y]));
  
           Fl[sz][s[i+len[y]]]=fl[sz]=y;
  
           ch[x][s[i]]=sz;
  
       }
  
       lst=x=ch[x][s[i]];
  
   }
  
   int main(){
  
       #ifndef ONLINE_JUDGE
  
       freopen("loj6070.in","r",stdin);
  
       freopen("loj6070.out","w",stdout);
  
       #endif
  
       typ=rd();n=rd();m=rd();
  
       u = sqrt(n);
  
       char c=gc();while(!isalpha(c))c=gc();
  
       for(int i=;i<=n;++i,c=gc()){
  
           bl[i]=(i-)/u+;ed[bl[i]]=i;
  
           if(!st[bl[i]])st[bl[i]]=i;
  
           s[i]=c-'a';
  
       }tot=bl[n];
  
       sz=;
  
       fl[]=;fl[]=;
  
       len[]=;len[]=-;
  
       for(rg int i=;i<;++i)Fl[][i]=;
  
       memset(end,0x3f,sizeof(end));
  
       for(rg int i=;i<=tot;++i){
  
           lst=;T++;
  
           for(rg int j=st[i];j<=n;++j){
  
               extend1(st[i],j);
  
               sum[i][j]=sum[i][j-];
  
               if(vis[lst]<T){
  
                   vis[lst]=T;
  
                   sum[i][j]++;
  
                   end[i][lst]=j;
  
               }
  
               if(len[lst]==j-st[i]+)pos[i][j]=lst;
  
               else pos[i][j]=pos[i][j-];
  
           }
  
       }
  
       int ans=;
  
       for(rg int i=,l,r;i<=m;++i){
  
           T++;
  
           l=rd();r=rd();
  
           if(typ)l^=ans,r^=ans;
  
           if(bl[l]==bl[r]){
  
               lst=;ans=;
  
               for(rg int j=l;j<=r;++j){
  
                   extend1(l,j);
  
                   if(vis[lst]<T)vis[lst]=T,ans++;
  
               }
  
           }else{
  
               ans=sum[bl[l]+][r];
  
               lst=pos[bl[l]+][r];
  
               for(rg int j=ed[bl[l]];j>=l;--j){
  
                   extend2(j,r);
  
                   if(vis[lst]<T&&end[bl[l]+][lst]>r)vis[lst]=T,ans++;
  
               }
  
           }
  
           printf("%d\n",ans);
  
       }
  
       return ;
  
   }

  loj6070