Migrated from Lutece 2827 破解机关

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上接解密程序

在确认了敌方老大的位置后，ljj 潜入了密会地点。但中途他被一道带机关的门卡住了，他必须破解这道机关才能完成刺杀。

一开始门上印着一个字符串 S，接下来机关会进行 m 次操作，操作分为两种：

第一种是在 S 后面插入一段字符串

第二种是询问某个字符串在 S 中的出现次数。

如果某次询问答错了，他就必须从头再来，重新破解机关，这让忙着刺杀的 ljj 感到更加烦躁，现在他联系到了作为算法竞赛大师的你，想让你帮助他破解这道门。机关为了提高安全性，还对操作进行了加密，我们只能一步步破解，因此你的程序必须是在线算法

Input

第一行读入 m，表示操作次数

第二行读入一个字符串 S，表示门上一开始印着的字符串。

接下来 m 行，每行两个字符串 op, str

如果 op = ADD ，则在 S 后面插入字符串 str

如果 op = QUERY，则询问 str 在 S 中的出现次数

你还需要维护一个变量mask，初始值为0

每次操作读入 str 后，你必须调用decode函数对字符串解密为真正的字符串，解密程序的代码如下：

#include <algorithm>
int mask=0;
void decode(){
    int tmp=mask;
    for (int j = 0; j < len; j++)
    {
        tmp = (tmp * 131 + j) % len;
        std::swap(str[j], str[tmp]);
    }
}

其中 len 是读入的字符串 str 的长度，swap 是交换函数，需要调用 algorithm 库中的函数

每次进行第二种操作询问完答案后，需要更新 mask 的值，更新方法是

mask ^= answer;

其中 answer 是此次询问的答案

Output

对每个询问的答案输出一行

Samples

5
ABABA
QUERY ABA
ADD BABAB
QUERY BAB
ADD BABBA
QUERY BA

0
1
5

Constraints

保证解密后的字符串只包含A和B两种字符

$Q\le 10^{4}$，最终 S 的长度 $|S|\le 6\times 10^{5},$，所有询问操作的 $\sum |str|\le 3\times 10^{6}$

Resources

2022 UESTC ICPC Training for String and Search Algorithm