Background

Reminder during the contest: The input for this problem uses Windows line endings, not Linux line endings, so there is an extra \r character before \n at the end of each line. Please use scanf or cin to read the input, rather than getline, because the latter will read an extra \r.

Problem Description

Little X is building a text editor and now needs to implement the most basic “find and replace” feature.

In the text editor, the file is stored as a string $a$ of length $n$.

Meanwhile, the user has a dictionary containing $m$ words. Each word is a string, and the $i$-th word is denoted by $s_i$.

Next, define the find and replace feature:

• Find: There are two parameters $l, r$, asking for the sum, over every word $s_i$ in the dictionary, of the number of occurrences of $s_i$ in $a[l : r]$.
  That is, compute $\displaystyle \sum_{i=1}^{m} \mathrm{occur}(s_i, a[l : r])$, where $\mathrm{occur}(s, t)$ denotes the number of occurrences of string $s$ in string $t$.

• Replace: There are three parameters $l, r, t$, where $t$ is a string, meaning to replace $a[l : r]$ with the result of repeating $t$ endlessly and taking the needed prefix.
  For example, if we replace $\texttt{Mds72SKsLL}$ with the endlessly repeated string $\texttt{Rabb}$, then the original string becomes $\texttt{RabbRabbRa}$.

The user provides $q$ operations, each being either find or replace. You need to output the correct answer for every find operation.

Input Format

The first line contains three integers $n, m, q$, representing the length of the file $a$, the number of words in the dictionary, and the number of queries.

The second line contains a string $a$ of length $n$, representing the initial file.

The next $m$ lines each contain a string; the $i$-th line is the $i$-th word $s_i$.

The next $q$ lines each describe an operation:
The first number on each line is $\mathrm{op}$, indicating the type of operation.
If $\mathrm{op} = 1$, then two integers $l, r$ follow, meaning this is a find operation with parameters $l, r$.
If $\mathrm{op} = 2$, then two integers $l, r$ and a string $t$ follow, meaning this is a replace operation with parameters $l, r, t$.

Output Format

For each find operation, output one integer per line, representing the answer to this find query.

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

Hint

This problem uses bundled testdata.

• Subtask 1 (7 points): $n, m, q \le 50$, all string lengths $\le 50$, time limit $1\text{s}$.
• Subtask 2 (7 points): $n, q \le 3000$, time limit $1\text{s}$.
• Subtask 3 (13 points): $m = 1$, time limit $2\text{s}$.
• Subtask 4 (17 points): There are no replace operations, i.e. $\mathrm{op} = 1$, time limit $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$, time limit $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$, time limit $1\text{s}$.
• Subtask 7 (25 points): No special constraints, time limit $2\text{s}$.

For $100\%$ of the data:
Constraints on $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 \}$.
Constraints on string lengths: $|s_i| \le 50$, $\displaystyle \sum |s_i| \le 2 \times 10^5$, $\displaystyle \sum |t| \le 10^6$.
All strings are guaranteed to be non-empty, and all characters belong to the set $\mathbf{\Sigma}$, where $\mathbf{\Sigma} = [\texttt a, \texttt z] \cup [\texttt A, \texttt Z] \cup [\texttt 0, \texttt 9]$, i.e. all lowercase letters, uppercase letters, and digits, so $|\mathbf{\Sigma}| = 62$.

A special note: Compared to the file, the words are very short. You may need to make use of this when solving the problem.

[Some definitions]

For a string $s$ of length $\mathrm{len}$, the notation $s[l : r]$ ($1 \le l \le r \le \mathrm{len}$) denotes the substring of $s$ from $l$ to $r$. That is, the string formed by concatenating the $l$-th through the $r$-th characters of $s (inclusive) in order. For a string$s$, the notation$|s|$ denotes its length.

Translated by ChatGPT 5