题目描述

译自 ROI 2019 Day2 T4. Поиск идеи

给出模式串 $p$，其长度为 $m$。又给出「压缩后的」文本串 $t$，试求 $p$ 在 $t$ 中出现的次数。两个字符串均只包含小写英文字母。

压缩后的 $t$ 分为 $n$ 个有顺序的块。块的类型及解压方式如下：

• 开始解压时 $t$ 为空串。
• $\tt1\it\ w$，其中 $w$ 是一个字符串。在解压过程中，当读取到这一块时，将 $w$ 放在 $t$ 的末尾。
• $\tt2\rm\ pos\ len$，将 $t_{\rm pos}$ 复制到 $t$ 的末尾，再将 $t_{\mathrm{pos}+1}$ 复制到 $t$ 的末尾……共复制 $\rm len$ 个字符。比如，如果 $t=\tt aba$，当前块为 $2\ 1\ 7$，则 $t$ 会变为 $\tt abaabaabaa$。

输入格式

$m,n$
$p$
接下来 $n$ 行，每行一个块

样例

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

6

开始：空串 读取第一块后：$\tt ab$ 读取第二块后：$\tt ababa$ 读取第三块后：$\tt ababaaba$ 读取第四块后：$\tt ababaabaababaaba$

$$\tt ababaabaababaaba\\aba\ \ aba\ \ aba\ \ \ \\\ \ aba\ \ \ aba\ \ aba$$

数据范围与提示

用 $L_i$ 表示读取第 $i$ 块后 $t$ 的长度。 如果第 $i$ 个块属于第二类块，我们用 $\mathrm{pos}_i$ 和 $\mathrm{len}_i$ 特指这个块的 $\rm pos$ 和 $\rm len$。

对于所有子任务，保证 $\sum |w_i|\le 2\times 10^5$。