Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
aPaPBbP
3
1 2
1 3
2 3
Sample Output
2
1
0
HINT
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5
首先我们建出ac自动机，然后对于一组询问（x，y）就是从根到y字符串这条路径有多少点可以通过fail走到x节点，然后fail反向建出来的是一棵树（就叫fail树算了）
于是一组询问（x，y）就是从根到y字符串这条路径有多少点在x节点的子树中，于是我们处理出dfs序，我们就只要维护区间和就行了
对于多组询问我们就离线处理，按照他打字机的顺序遍历点，小写字母就在他的dfs序上+1，B就在现在这个节点的dfs序上-1，走到x单词的结束节点时处理询问（i，x）
const
maxn=;
type
node=record
x,y,id:longint;
end;
var
go:array[..maxn,'a'..'z']of longint;
q:array[..maxn]of node;
ch:array[..maxn]of char;
e,p,fa,ll,rr,ans,fail,first,last,next,bit:array[..maxn]of longint;
n,cnt,tot,now,sum:longint;
s:ansistring; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; function nexts(x:longint;c:char):longint;
begin
if go[x,c]= then
begin
inc(cnt);go[x,c]:=cnt;
fa[cnt]:=x;ch[cnt]:=c;
end;
exit(go[x,c]);
end; procedure swap(var x,y:node);
var
t:node;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint);
var
i,j,y:longint;
begin
i:=l;j:=r;y:=q[(l+r)>>].x;
repeat
while q[i].x<y do inc(i);
while q[j].x>y do dec(j);
if i<=j then
begin
swap(q[i],q[j]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end; procedure dfs(x:longint);
var
i:longint;
begin
inc(sum);ll[x]:=sum;
i:=first[x];
while i<> do
begin
dfs(last[i]);
i:=next[i];
end;
rr[x]:=sum;
end; var
que:array[..maxn]of longint;
l,r:longint; procedure bfs;
var
i,j:longint;
c:char;
begin
que[]:=;l:=;r:=;
while l<=r do
begin
for c:='a' to 'z' do
if go[que[l],c]> then
begin
inc(r);
que[r]:=go[que[l],c];
end;
inc(l);
end;
for i:= to cnt do
begin
j:=que[i];c:=ch[j];j:=fail[fa[j]];
while (j<>) and (go[j,c]=) do
j:=fail[j];
fail[que[i]]:=go[j,c];
if fail[que[i]]=que[i] then fail[que[i]]:=;
insert(fail[que[i]],que[i]);
end;
end; function get(x:longint):longint;
begin
get:=;
while x> do
begin
inc(get,bit[x]);
x:=x-(x and (-x));
end;
end; procedure add(x,y:longint);
begin
while x<=sum do
begin
inc(bit[x],y);
x:=x+(x and (-x));
end;
end; procedure main;
var
i,j:longint;
begin
readln(s);now:=;
for i:= to length(s) do
begin
if s[i]='P' then
begin
inc(n);
e[n]:=i;
p[n]:=now;
end
else
if s[i]='B' then now:=fa[now]
else now:=nexts(now,s[i]);
end;
bfs;
dfs();
read(n);
for i:= to n do
read(q[i].y,q[i].x);
for i:= to n do q[i].id:=i;
sort(,n);
j:=;now:=;
for i:= to n do
begin
while j<e[q[i].x] do
begin
inc(j);
if s[j]='B' then
begin
add(ll[now],-);
now:=fa[now];
end
else
if s[j]<>'P' then
begin
now:=nexts(now,s[j]);
add(ll[now],);
end;
end;
ans[q[i].id]:=get(rr[p[q[i].y]])-get(ll[p[q[i].y]]-);
end;
for i:= to n do writeln(ans[i]);
end; begin
main;
end.