Migrated from Lutece 2628 字典序

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

给出一个初始字符串 $S$，你需要执行 $n$ 个操作。

• 增加：在字符串 $S$ 开始增加一个字符 $c$。
• 删除：删除 $S$ 的第一个字符。
• 询问：询问 $S$ 有多少子串字典序小于 $t$（出现位置不同记为不同的子串）。

此题目已对输入进行加密。你需要维护一个初始值为 $0$ 的变量 $\text{lastans}$，并在每次询问后将其置为该次询问的答案。每当你需要输入一个小写字母时，假设读入字母的 ASCII 码是 $c$，那么真实的字母的 ASCII 码为 $97+(((c-97)\oplus \text{lastans})\bmod 26)$。其中 $\oplus$ 表示按位异或运算。

Input

第一行一个字符串 $S$； 第二行一个正整数 $n$； 接下来 $n$ 行，每行第一个整数代表操作类型：

1. 增加，此行还有一个空格以及一个字符 $c$；
2. 删除；
3. 询问，此行还有一个空格以及一个字符串 $t$。

Output

对于每个询问，一行一个整数代表答案。

Samples

abba
4
1 a
3 aa
2
3 dd

3
2

Constraints

$1 \le |s| \le 10^6$ $1 \le n \le 5\times 10^5$ $1 \le |t| \le 20$ $1\le \sum |t|\le 2\times 10^6$

Resources

2021 UESTC ICPC Training for String and Search Algorithm