该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

题目背景

日记非常喜欢用记事本写代码。但是，由于记事本的性能优化很差，她的电脑经常卡死。所以她希望实现一个负载计算器来分析电脑为什么会卡死。

题目描述

日记使用的编程语言是 Neko Lang，这是一种只使用小写字母的编程语言。语言中有一个模式串 $P = P_1 \dots P_{|P|}$。设她当前的字符串为 $S = S_1 \dots S_{|S|}$，她只进行五种操作：

操作的参数中，除 $s, c$ 外均为非负整数，而 $s$ 为只包含小写字母的字符串，$c$ 为小写字母。

• Insert p s 在第 $p$ 个字符后插入字符串 $s$，使 $S \gets S_1 \dots S_p s_1 \dots s_{|s|} S_{p+1} \dots S_{|S|}$。若 $p=0$ 则为在字符串开头插入。
• Delete l r 删除第 $l$ 到第 $r$ 个字符，使 $S \gets S_1 \dots S_{l-1} S_{r+1} \dots S_{|S|}$。
• Replace l r s 将第 $l$ 到第 $r$ 个字符替换为字符串 $s$，使 $S \gets S_1 \dots S_{l-1} s_1 \dots s_{|s|} S_{r+1} \dots S_{|S|}$。
• Count l r c 输出第 $l$ 到第 $r$ 个字符间字母 $c$ 的个数，即 $\sum\limits_{i=l}^r [S_i = c]$。
• Search l r 输出第 $l$ 到第 $r$ 个字符间模式串 $P$ 的出现次数，即 $\sum\limits_{i=l}^{r-|P|+1} \min\limits_{j=1}^{|P|} [S_{i+j-1} = P_j]$。

日记认定，是她使用了太多次查询操作，使得电脑卡死了。所以，你需要帮助日记计算出两种查询操作的结果，这样日记就可以确认自己的想法了。

输入格式

第 $1$ 行，$1$ 个正整数 $n$ 和 $1$ 个字符串 $P$，其中 $n$ 为操作次数。

接下来 $n$ 行，每行按上述格式描述一次操作。

输出格式

每次查询操作 $1$ 行，为对应操作的结果。

数据范围

本题设置 25 个测试点，每个测试点 4 分。同时，记五种操作的次数依次为 $a_1 \dots a_5$，每个测试点满足一些限制，见下：

测试点编号	$n \leq$	$a_i$
$1$	$10$	$a_5=0$
$2$
$3$	$100$	$a_2=a_3=a_5=0$
$4$		$a_5=0$
$5$
$6$	$10^3$	$a_2=a_3=a_5=0$
$7$		$a_3=a_5=0$
$8$		$a_5=0$
$9$
$10$
$11$	$10^4$	$a_2=a_3=a_5=0$
$12$		$a_3=a_5=0$
$13$		$a_5=0$
$14$
$15$
$16$	$10^5$	$a_2=a_3=a_5=0$
$17$		$a_3=a_5=0$
$18$
$19$		$a_5=0$
$20$
$21$		$a_5 \leq 10$
$22$		$a_5 \leq 100$
$23$
$24$
$25$

对全部数据，保证 $1 \leq n \leq 10^5$，$|s| \leq 10^5$，$\sum |s| \leq 10n$，$|P| \leq 20$。

输入样例 1

8 abababc
Insert 0 abababababababab
Search 1 16
Count 1 16 a
Replace 7 8 cabc
Search 1 18
Count 1 18 c
Insert 7 abab
Search 1 14

输出样例 1

0
8
1
2
2

输入样例 2

2 ababab
Insert 0 abababababababab
Search 1 16

输出样例 2

6

样例解释

样例解释 1

每个操作结束后，字符串依次为：

abababababababab
abababababababab
abababababababab
abababcabcabababab
abababcabcabababab
abababcabcabababab
abababcabababcabababab
abababcabababcabababab

样例解释 2

注意，两个匹配的范围可以重叠。如果你不理解这句话的含义，请仔细阅读题目描述中匹配的形式化定义。