题目描述
译自 ROI 2019 Day2 T4. Поиск идеи

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

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

开始解压时 $t$ 为空串。

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

---

输入格式
$m,n$
$p$
接下来 $n$ 行，每行一个块。

---

样例
输入

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

输出

6

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

$$\begin{array}{c} \texttt{ababaabaababaaba}\\ \underline{\texttt{aba}}\ \ \texttt{aba}\ \ \texttt{aba}\ \ \ \ \\ \ \ \texttt{aba}\ \ \ \texttt{aba}\ \ \texttt{aba} \end{array} $$

---

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

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

---