【XR-4】文本编辑器

**赛时提醒：本题输入数据是 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|$ 表示它的长度。