JZPSTR

初始字符串为空。你需要对该字符串进行以下三种操作：

• 插入操作：在位置 $x_i$ 处插入字符串 $y_i$。插入后，字符串 $y_i$ 的首字符下标为 $x_i$；
• 删除操作：删除下标区间 $[x_i,y_i)$ 内的字符串；
• 查询操作：查询下标区间 $[x_i,y_i)$ 内的字符串包含多少次给定子串 $z_i$。

字符串下标从 $0$ 开始，即第一个字符的下标为 $0$。所有区间均为左闭右开区间，即 $[x_i,y_i)$ 包含下标 $x_i$，但不包含下标 $y_i$。

输入格式

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

接下来 $T$ 行，每行首先包含一个整数 $p_i$，表示操作类型：

• 若 $p_i=0$，则接下来输入一个整数 $x_i$ 和一个字符串 $y_i$，表示在位置 $x_i$ 处插入字符串 $y_i$；
• 若 $p_i=1$，则接下来输入两个整数 $x_i$ 和 $y_i$，表示删除下标区间 $[x_i,y_i)$ 内的字符串；
• 若 $p_i=2$，则接下来输入两个整数 $x_i$、$y_i$ 和一个字符串 $z_i$，表示查询下标区间 $[x_i,y_i)$ 内的字符串包含多少次子串 $z_i$。

保证所有操作均合法。

输出格式

对于每个查询操作，输出一行一个整数，表示该查询的答案。

样例输入

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

数据范围

• 所有插入和查询操作中给出的字符串均非空，且仅包含字符 $0$ 到 $9$；
• 所有查询区间和删除区间均非空；
• 保证输入数据合法。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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