[Noi2011]阿狸的打字机

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

这台打字机的工作方式如下：

• 按下小写字母键时，打字机的凹槽末尾会加入对应的字母；
• 按下 B 键时，凹槽中的最后一个字母会消失；
• 按下 P 键时，打字机会将凹槽中现有的所有字母打印在纸上并换行，但凹槽中的字母不会消失。

保证操作过程中，每次按下 B 键前凹槽均非空。换言之，在操作字符串的任意前缀中，小写字母的数量均不少于 B 的数量。

例如，阿狸依次输入 aPaPBbP，纸上会打印出：

a
aa
ab

将纸上打印出的字符串按照打印顺序从 $1$ 到 $n$ 编号。打字机中还暗藏了一个带数字的小键盘。在小键盘上输入两个整数 $(x,y)$，其中 $1\le x,y\le n$，打字机便会显示第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

打字机允许打印空字符串。若第 $x$ 个打印的字符串为空，则规定它在长度为 $k$ 的字符串中出现 $k+1$ 次，分别对应字符串中所有相邻字符之间的边界以及字符串的首尾位置。

请编写程序，实现这一功能。

输入格式

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

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

接下来 $m$ 行，每行包含两个整数 $x,y$，表示询问第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

输出格式

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

样例输入

aPaPBbP

3

1 2

1 3

2 3

样例输出

2
1
0

数据范围

令 $L$ 为第一行操作字符串的长度，$n$ 为操作字符串中字符 P 的数量。

• $1\le L\le 10^5$；
• $1\le n\le 10^5$；
• $1\le m\le 10^5$；
• 每个询问均满足 $1\le x,y\le n$；
• 第一行操作字符串仅由小写英文字母、B 和 P 组成。

来源与许可

本题为 NOI 2011 试题「阿狸的打字机」，题面与测试数据整理自 BZOJ。

样例 1

输入

aPaPBbP

3

1 2

1 3

2 3

输出

2
1
0