【模板】后缀平衡树
题目背景
"后缀平衡树"这个名字正确性存疑，由于 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$ 操作，输出一行一个整数表示答案。
输入输出样例
输入样例 #1
3
A
QUERY B
ADD BBABBBBAAB
DEL 1输出样例 #1
0说明
数据字符串变化长度以及初始长度和 $ \le 8 \times 10^5$，询问次数 $\le 10^5$，询问总长度 $\le 3 \times 10^6$。
字符集为大写字母，注意 `ADD` 和 `QUERY` 操作的字符串都需要解压。