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:


Sample Output:


题解:


AC自动机不太熟,这种题真心调了很久 [摊手]

首先处理字符串,插入AC自动机中,注意不能够分开插入,如果p每一次都从1开始可能会TLE。然后getfail一下(这里不能够把fail数组合并进ch中),注意到fail指针形成了一棵树,Trie也形成了一棵树。

对于一个询问 \((x, y)\) ,如果在从1节点到 \(y\) 节点的路径上某一个点可以一路fail到 \(x\) 节点,那么询问的答案加1。转换一下思路,答案就是从1节点到 \(y\) 节点中有多少个在 \(x\) 节点的fail子树中。

考虑fail树的dfs序列(进入节点离开节点分别在l[i], 和r[i]),如果我们把1节点到 \(y\) 节点路径上的每一个点标记一下,那么 \([l[x], r[x]]\) 中的标记数就是答案。

考虑用树状数组维护fail树的dfs序列,我们在Trie树上dfs,进入时l[i]加1,离开时l[i]减1,中间处理以该节点为y的询问。

代码如下: