题目背景

赛时提醒：本题输入数据是 Windows 格式，而非 Linux 格式，所以在每一行末尾的 \n 之前有一个多余的 \r 字符。请使用 scanf 或 cin 读入数据，而非 getline，因为后者会多读入一个 \r。

题目描述

小 X 在制作一个文本编辑器，现在需要实现最基本的“查找和替换”功能。

在文本编辑器中，文件是以一个长度为 $n$ 的字符串 $a$ 的形式存储的。

同时，用户拥有一个包含 $m$ 个单词的字典，每个单词都是一个字符串，称第 $i$ 个单词为 $s_i$。

接下来定义查找和替换功能：

• 查找功能：有两个参数 $l, r$，表示询问对于字典中的每个单词 $s_i$，$a[l : r]$ 中 $s_i$ 的出现次数之和。
  即询问 $\displaystyle \sum_{i=1}^{m} \mathrm{occur}(s_i, a[l : r])$，其中 $\mathrm{occur}(s, t)$ 表示字符串 $s$ 在字符串 $t$ 中的出现次数。

• 替换功能：有三个参数 $l, r, t$，其中 $t$ 是一个字符串，表示将 $a[l : r]$ 替换为 $t$ 不断重复的结果。
  即如果把 $\texttt{Mds72SKsLL}$ 替换为 $\texttt{Rabb}$ 不断重复的结果，则原字符串变为 $\texttt{RabbRabbRa}$。

用户给出了 $q$ 个操作，每个操作是查找或替换之一，你需要正确回答每个查找操作的答案。

输入格式

第一行三个整数 $n, m, q$，依次表示文件 $a$ 的长度，字典中的单词数，询问的个数。

第二行一个长度为 $n$ 的字符串 $a$，表示初始文件。

接下来 $m$ 行，第 $i$ 行一个字符串，表示第 $i$ 个单词 $s_i$。

接下来 $q$ 行，每行表示一个操作：
每行的第一个数 $\mathrm{op}$ 表示此次操作的类型；
若 $\mathrm{op} = 1$，则接下来两个整数 $l, r$，表示这是一次查找操作，参数为 $l, r$；
若 $\mathrm{op} = 2$，则接下来两个整数 $l, r$ 和一个字符串 $t$，表示这是一次替换操作，参数为 $l, r, t$。

输出格式

对于每个查找操作，一行一个整数，表示本次查找操作的答案。

6 2 5
BBABBA
BB
BAB
1 1 6
2 3 5 A
1 2 3
2 1 6 B
1 1 5

3
0
4

提示

本题采用捆绑测试。

• Subtask 1（7 points）：$n, m, q \le 50$，所有字符串长度 $\le 50$，时限 $1\text{s}$。
• Subtask 2（7 points）：$n, q \le 3000$，时限 $1\text{s}$。
• Subtask 3（13 points）：$m = 1$，时限 $2\text{s}$。
• Subtask 4（17 points）：没有替换操作，即 $\mathrm{op} = 1$，时限 $2\text{s}$。
• Subtask 5（18 points）：$n, q \le 8 \times 10^4$，$\displaystyle \sum |s_i| \le 50$，$\displaystyle \sum |t| \le 8 \times 10^4$，时限 $1\text{s}$。
• Subtask 6（13 points）：$n, q \le 5\times 10^4$，$\displaystyle \sum |s_i| \le 5\times 10^4$，$\displaystyle \sum |t| \le 5\times 10^4$，时限 $1\text{s}$。
• Subtask 7（25 points）：无特殊限制，时限 $2\text{s}$。

对于 $100\%$ 的数据：
对 $n, m, q, l, r, \mathrm{op}$ 的限制：$1 \le l \le r \le n \le 10^6$，$1 \le m, q \le 10^5$，$\mathrm{op} \in \{ 1, 2 \}$。
对字符串长度的限制：$|s_i| \le 50$，$\displaystyle \sum |s_i| \le 2 \times 10^5$，$\displaystyle \sum |t| \le 10^6$。
所有字符串保证不为空串，且出现的字符属于集合 $\mathbf{\Sigma}$，其中 $\mathbf{\Sigma} = [\texttt a, \texttt z] \cup [\texttt A, \texttt Z] \cup [\texttt 0, \texttt 9]$，即所有大小写英文字母以及数字，故 $|\mathbf{\Sigma}| = 62$。

需要特别注意的是，与文件相比，单词的长度是非常小的。在解题时你可能需要利用这一点。

【一些定义】

对于一个长度为 $\mathrm{len}$ 的字符串 $s$，符号 $s[l : r]$（$1 \le l \le r \le \mathrm{len}$）表示 $s$ 中从 $l$ 到 $r$ 的子串。即 $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含端点）连续拼接在一起形成的字符串。
对于一个字符串 $s$，符号 $|s|$ 表示它的长度。