阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和‘B‘、‘P‘两个字母。

经阿狸研究发现，这个打字机是这样工作的：

l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有‘B‘的按键，打字机凹槽中最后一个字母会消失。

l 按一下印有‘P‘的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

 输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m，表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。

 输出m行，其中第i行包含一个整数，表示第i个询问的答案。

 1<=N<=10^5

  1 #include<cstdio>  2 #include<cstring>  3 const int maxn = 200005;  4 char str[maxn];  5 int n,m;  6 int a[maxn][29],point[maxn],fa[maxn],q[maxn],sz=1;  7 int pos[maxn];  8    9 void ins(){ 10     int now=1,id=0; 11     n=strlen(str); 12     for(int i=0;i<n;i++){ 13         if(str[i]==‘P‘){ 14             pos[++id]=now; 15             continue; 16         }else if(str[i]==‘B‘){ 17             now=fa[now]; 18             continue; 19         } 20         else{ 21             int k=str[i]-‘a‘+1; 22             if(a[now][k]){ 23                 fa[a[now][k]]=now; 24                 now=a[now][k]; 25             }else{ 26                 a[now][k]=++sz; 27                 fa[a[now][k]]=now; 28                 now=a[now][k]; 29             } 30         } 31     } 32 } 33 void acm(){ 34     for(int i=1;i<=27;i++)a[0][i]=1; 35     int l=0,r=0; 36     q[r++]=1;point[1]=0; 37     while(l<r){ 38         int now=q[l++]; 39         for(int i=1;i<=27;i++){ 40             if(!a[now][i])continue; 41             int k=point[now]; 42             while(!a[k][i])k=point[k]; 43             point[a[now][i]]=a[k][i]; 44             q[r++]=a[now][i]; 45         } 46     } 47 } 48 int h[maxn],nx[maxn<<1],to[maxn<<1],cnt; 49 void add_edge(int u,int v){ 50     to[++cnt]=v;nx[cnt]=h[u];h[u]=cnt; 51 } 52 void link(int u,int v){ 53     add_edge(u,v);add_edge(v,u); 54 } 55 void build_fail(){ 56     for(int i=1;i<=sz;i++){ 57         link(i,point[i]); 58     } 59 } 60 int hq[maxn],nxq[maxn<<1],toq[maxn<<1],cntq; 61 int l[maxn],r[maxn],dfs_clock,dfn[maxn]; 62 void add_edgeq(int u,int v){ 63     toq[++cntq]=v;nxq[cntq]=hq[u];hq[u]=cntq; 64 } 65 void dfs(int x,int pr){ 66 //  printf("%d %d\n",x,dfs_clock); 67 //  dfn[++dfs_clock]=x; 68     l[x]=++dfs_clock; 69     for(int i=h[x];i;i=nx[i]){ 70         if(to[i]==pr)continue; 71         dfs(to[i],x); 72     } 73     r[x]=++dfs_clock; 74 } 75 int fenwick[maxn]; 76 void add(int x,int delta){ 77     while(x<=dfs_clock){ 78         fenwick[x]+=delta; 79         x+=(x&(-x)); 80     } 81 } 82 int sum(int x){ 83     int rt=0; 84     while(x){ 85         rt+=fenwick[x]; 86         x-=(x&(-x)); 87     } 88     return rt; 89 } 90 int ans[maxn]; 91 void solve(){ 92     int now=1,id=0; 93     add(l[1],1); 94     for(int i=0;i<n;i++){ 95         if(str[i]==‘P‘){ 96             id++; 97             for(int x=hq[id];x;x=nxq[x]){ 98                 int t=pos[toq[x]]; 99                 ans[x]=sum(r[t])-sum(l[t]-1);100             }101         }else if(str[i]==‘B‘){102             add(l[now],-1);now=fa[now];103         }104         else{105             now=a[now][str[i]-‘a‘+1];106             add(l[now],1);107         }108     }109 }110 int main(){111     scanf("%s",str);112     ins();113     acm();114     build_fail();115     dfs(0,0);116      117     scanf("%d",&m);118     for(int i=1;i<=m;i++){119         int _a,_b;120         scanf("%d%d",&_a,&_b);121         add_edgeq(_b,_a);122     }123     solve();124     for(int i=1;i<=m;i++)printf("%d\n",ans[i]);125     return 0;126  127 }128