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