题目描述

三〇一九年，考古学家在古城市 Innopolis 进行挖掘时，发现了一件古代遗物——一个硬盘。硬盘中有一个文件，据推测，其中保存了所有 ROI 题目的文本。

研究发现，文件内容被编码成一个由小写英文字母组成的字符串 $t$。由于题目文本很长，并且有许多重复内容，所以文件以压缩形式存储。

解压缩过程如下。

初始时，字符串 $t$ 为空。压缩文件包含 $n$ 个块，按顺序处理。每个块有以下两种类型之一：

• 1 w：其中 $w$ 是一个字符串。处理该块时，将字符串 $w$ 追加到 $t$ 的末尾。
• 2 pos len：其中 $pos$ 和 $len$ 是正整数。假设当前字符串 $t$ 的字符从 $1$ 开始编号。处理该块时，将 $t$ 中从位置 $pos$ 开始的连续 $len$ 个字符依次追加到 $t$ 的末尾。若 $len$ 足够大，则本次刚追加的字符也可能在处理同一块时继续被使用。

考古学家想统计某个算法在 ROI 中被考察的次数。为此，他们给定一个由小写英文字母组成的模式串 $p$，并希望求出 $p$ 在最终解压出的字符串 $t$ 中作为子串出现的次数。

若长度为 $m$ 的字符串 $p$ 从 $t$ 的位置 $i$ 开始出现，则 $t_i,t_{i+1},\ldots,t_{i+m-1}$ 与 $p$ 完全相同。出现位置可以重叠。

请输出 $p$ 在解压缩后的字符串 $t$ 中出现的次数。

输入格式

第一行包含两个自然数 $m,n$，分别表示模式串 $p$ 的长度和压缩文本中的块数。

第二行包含一个非空字符串 $p$，仅由小写英文字母组成。

接下来 $n$ 行，每行描述一个块，格式为题目描述中的 1 w 或 2 pos len。

输出格式

输出一个整数，表示字符串 $p$ 在解压缩后文本 $t$ 中出现的次数。

样例一

输入

3 4
aba
1 ab
2 1 3
2 3 3
2 1 8

输出

6

解释

解压缩过程为：

$$\text{ab}\to \text{ababa}\to \text{ababaaba}\to \text{ababaabaababaaba}.$$

aba 在 ababaabaababaaba 中出现了 $6$ 次。

样例二

输入

16 15
ilovethisproblem
1 ilovethisproblem
2 1 16
2 1 32
2 1 64
2 1 128
2 1 256
2 1 512
2 1 1024
2 1 2048
2 1 4096
2 1 8192
2 1 16384
2 1 32768
2 1 65536
2 1 131072

输出

16384

样例三

输入

20 10
aaaaaaaaaaaaaaaaaaaa
1 aaaaaaaaaaaaaaaaaaaamusoraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaamnogomusoraaaaaaaaaaaaaaaaaaaaa
2 19 1
2 18 2
2 17 3
2 16 4
2 15 5
2 14 6
2 13 7
2 12 8
2 11 9

输出

69

样例四

见原题附件。

数据范围与子任务

设将前 $i$ 块解压缩后字符串的长度为 $L_i$，第 $i$ 块的类型为 $type_i$。

子任务	分值	$m\le$	$n\le$	$L_n\le$	其它特殊性质
1	6	2000	1	1000	-
2	10	$10^5$	2000	$10^6$
3		2000		$10^{10}$	对所有 $i>1$，$type_i=2,pos_i=1,L_1\mid len_i$
4					$pos_i=L_{i-1}$
5		20			$pos_i=1,len_i\le 10^7$
6	4	2000
7	10	20			$p$ 只含字母 a，且 $pos_i+len_i-1\le L_{i-1}$
8	6				$pos_i+len_i-1\le L_{i-1}$
9	2	1	2000		$p$ 只含字母 a
10	4	20
11	5				-
12	14	$10^5$
13	9	$2\times 10^5$	10000	$10^{15}$

对于 $100\%$ 的数据，保证

$$\sum |w|\le 2\times 10^5,$$

其中求和只对所有类型为 1 w 的块中的字符串 $w$ 计算。