题目描述

你要对一个字符串进行三种操作：

1. 在位置 $x_i$ 处插入一个字符串 $y_i$。
2. 删除位置 $[x_i, y_i)$ 的字符串。
3. 查询位置 $[x_i, y_i)$ 的字符串包含多少次给定的子串 $z_i$。

输入格式

第一行，一个整数 $T$，表示操作个数。

下面 $T$ 行，每行第一个数 $p_i$，表示这个操作的类型：

• 若 $p_i=0$，则接下来有一个整数 $x_i$ 和一个字符串 $y_i$，表示进行插入操作；
• 若 $p_i=1$，则接下来有两个整数 $x_i$ 和 $y_i$，表示进行删除操作；
• 若 $p_i=2$，则接下来有两个整数 $x_i$ 和 $y_i$，以及一个字符串 $z_i$，表示进行询问。

字符串的下标从 $0$ 开始(即第一个字符的下标为 $0$)。

初始时字符串为空。

对于插入操作，插入后字符串 $y_i$ 的首字符的下标应为 $x_i$；

对于删除操作，删除的区间 $[x_i, y_i)$ 为左闭右开区间；

对于查询操作，询问的区间 $[x_i, y_i)$ 为左闭右开区间。

所有插入的和查询的字符串均不为空，且只包含 $0\sim9$ 的字符。

所有询问的区间和删除的区间均不为空。保证输入数据合法。

对于"左闭右开区间"不理解的可以去看样例解释。

输出格式

对每个询问操作，输出一行，表示这个询问的答案。

8
0 0 894894894
2 0 2 894
2 0 9 894
0 2 6
2 0 9 64
2 0 9 894
1 2 6
2 0 6 894

0
3
1
1
2

样例解释

第一次操作后，字符串为 $894894894$；
第二次操作，询问的区间为 $89$，不包含任何 $894$； 第三次操作，询问的区间为 $894894894$，包含三个 $894$；
第四次操作后，字符串为 $8964894894$；
第五次操作，询问的区间为 $896489489$，包含一个 $64$；
第六次操作，询问的区间为 $896489489$，包含一个 $894$；
第七次操作后，字符串为 $894894$；
第八次操作，询问的区间为 $894894$，包含两个 $894$。

数据规模和约定

$50\%$ 的数据中，询问个数 $\leq100$ (不是操作个数)。
$100\%$ 的数据中，插入总长度$\leq 2000000$，任何时刻字符串长度$\leq 1000000$，插入次数 $\leq 1001$，删除次数 $\leq 1000$，询问的 $z_i$ 的总长度 $\leq 10000$。