题目描述

wxh 太强了，他觉得你们太菜了，所以懒得写背景了，给你一个字符串 $init$，要求你支持三个操作。

1. 在当前字符串的后面插入若干个字符；
2. 在当前字符串的后面删除若干个字符；
3. 询问字符串 $s$ 在当前字符串中出现了几次？（作为连续子串）。

你必须在线支持这些操作。

输入格式

第一行一个数 $Q$ 表示操作个数。
第二行一个字符串表示初始字符串 $init$。
接下来 $Q$ 行，每行 $2$ 个字符串 $Type,Str$。
$Type$ 是 ADD 的话表示在后面插入。 $Type$ 是 DEL 的话表示在后面删除。 $Type$ 是 QUERY 的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量 $mask$，初始值为 $0$。
读入串 $Str$ 之后，使用这个过程将之解码成真正询问的串 $TrueStr$。
询问的时候，对 $TrueStr$ 询问后输出一行答案 $Result$。
然后 $mask = mask \operatorname{xor} Result$。
插入的时候，将 $TrueStr$ 插到当前字符串后面即可。

提示：ADD 和 QUERY 操作的字符串都需要解压。

输出格式

无

3
A
QUERY B
ADD BBABBBBAAB
DEL 1

0

数据规模与约定

对于 $100\%$ 的数据，字符集大写字母。
数据字符串变化长度以及初始长度和 $\le 6\times 10^5$，询问次数 $\le 10^4$，询问总长度 $\le 3\times 10^6$。

提示

应出题人要求放出数据如下：http://www.lydsy.com/JudgeOnline/upload/wxh.zip。

题目来源

By nzhtl1477