题目背景

"后缀平衡树"这个名字正确性存疑，由于 clj 给的"重量平衡树"定义有歧义。

字符串我也不会，所以也没去查证。

题目描述

给你一个字符串 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 xor Result

插入的时候，将 TrueStr 插到当前字符串后面即可。

输出格式

对每个 $3$ 操作，输出一行一个整数表示答案。

3
A
QUERY B
ADD BBABBBBAAB
DEL 1

0

提示

数据字符串变化长度以及初始长度和 $\le 8 \times 10^5$，询问次数 $\le 10^5$，询问总长度 $\le 3 \times 10^6$。

字符集为大写字母，注意 ADD 和 QUERY 操作的字符串都需要解压。