Description

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

0. 在位置 $x_i$ 处插入一个字符串 $y_i$；

1. 删除位置 $[x_i, y_i)$ 的字符串；

2. 查询位置 $[x_i, y_i)$ 的字符串包含多少次给定的子串 $z_i$。

Input Format

第一行，一个整数 $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)$ 为左闭右开区间。

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

所有询问的区间和删除的区间均不为空。

保证输入数据合法。

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

Output Format

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

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

Hint

样例解释：

• 第一次操作后，字符串为 $\texttt{894894894}$；

• 第二次操作，询问的区间为 $\texttt{89}$，不包含任何 $\texttt{894}$；

• 第三次操作，询问的区间为 $\texttt{894894894}$，包含三个 $\texttt{894}$；

• 第四次操作后，字符串为 $\texttt{8964894894}$；

• 第五次操作，询问的区间为 $\texttt{896489489}$，包含一个 $\texttt{64}$；

• 第六次操作，询问的区间为 $\texttt{896489489}$，包含一个 $\texttt{894}$；

• 第七次操作后，字符串为 $\texttt{894894}$；

• 第八次操作，询问的区间为 $\texttt{894894}$，包含两个 $\texttt{894}$。

数据范围：

• $50\%$ 的数据中，询问个数 $\le100$ （不是操作个数）；

• $100\%$ 的数据中，插入总长度 $\le 2\times10^6$，任何时刻字符串长度 $\le 10^6$，插入次数 $\le 1001$，删除次数 $\le 1000$，询问的 $z_i$ 的总长度 $\le 10^4$。

来源：2012 集训队互测，by gyz