题目描述

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

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

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

2. 查询位置$[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~9的字符。

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

保证输入数据合法。

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

输出格式

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

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%的数据中，询问个数<=100 (不是操作个数)

100%的数据中，插入总长度<=2000000，任何时刻字符串长度<=1000000，插入次数<=1001，删除次数<=1000，询问的z_i的总长度<=10000

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