Migrated from Lutece 3065 好厉害的数据结构

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

Natsuzora 要你写一个好厉害的数据结构！

你需要维护一个字符串 $S$。给定 $S$ 的初始状态 $S_0$，你要支持以下三种操作：

• 给出一个串 $T_{add}$，你需要将其拼接到 $S$ 的尾部；

• 给定整数 $k$，你需要从 $S$ 的尾部弹出 $K$ 个字符；

• 给定串 $T_{ask}$，询问 $T_{ask}$ 在 $S$ 中以子串的形式出现了多少次？

Natsuzora 希望你的数据结构能在线地支持这些操作。

Input

第一行一个字符串，表示 $S_0$；

第二行一个整数 $q$，表示操作次数；

对于每次操作，首先输入一个整数 $opt$，表示操作类型。对于每种操作类型：

$opt=1$ 表示当前操作为插入操作。接下来，输入一个字符串 $F$，你需要将其解密成真正的字符串 $T_{add}$，再将其插入到 $S$ 的尾部；

$opt=2$ 表示当前操作为删除操作。接下来，输入一个整数 $k$，表示你需要弹出字符串尾部的 $k$ 个字符。整数 $k$ 是没有被加密的；

$opt=3$ 表示当前操作为询问操作。接下来，输入一个字符串 $F$，你需要将其解密成真正的字符串 $T_{ask}$，再回答 $T_{ask}$ 在 $S$ 中作为子串出现了多少次。 $\text{}$ 为了解密字符串 $F$，你需要维护一个变量 $mask$，最开始 $mask=0$。你需要使用以下代码来解密 $F$：

void decodeWithMask(char s[], int mask) {
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		mask = (mask * 131 + i) % len;
		swap(s[i], s[mask]);
	}
}

每当完成一次询问时，你需要令 $mask :=mask\oplus result$，其中 $\oplus$ 表示异或运算，$result$ 表示这次询问的结果。

Output

对于每次询问操作，输出一行一个整数表示答案。

Samples

3
abba
2 1
1 babbbab
3 a

3

Constraints

$1\le q\le 10^5$ $S_0,k,|T_{add}|,|T_{ask}|\ge 1$ $S_0+k+\sum |T_{add}|\le 5\times 10^5$ $\sum |T_{ask}|\le 2\times 10^6$

数据保证给定的任何字符串中仅包含小写英文字母。

Resources

2023 UESTC ICPC Training for String