String Transformation and Historical Query

You are given m types of characters numbered from 0 to m-1. A string is formed by a sequence of these characters.

Initially, you are given n strings (which may be empty) indexed from 1 to n. Then, you must process q operations. Operations are numbered sequentially starting from 1. Note that all operations count toward the numbering, including queries.

An important concept in this problem is the following: For integers \(l\) and \(r\) with \(0 \le l \le r < m\), we say that a string \(s\) can be made equal to string \(t\) via the range \([l, r]\) if there exists a character \(d\) with \(l \le d \le r\) (where \(d\) denotes its numeric id) such that if you prepend the character corresponding to \(d\) to \(s\), you obtain \(t\). In other words, \(t = d + s\) and note that necessarily \(|t| = |s| + 1\); also, the condition requires that \(d\) (which is the first character of \(t\)) lies in the interval \([l, r]\).

There are four types of operations:

1. Operation 0: 0 x c. Append character c to the end of the x-th string. It is guaranteed that \(1 \le x \le n\) and \(0 \le c < m\).
2. Operation 1: 1 x y k l r. In the current state of string \(x\), count the number of substrings sub that satisfy the following property: Let \(P\) be the state of string \(y\) immediately after the k-th operation (if \(k = 0\), this means the initial state before any operation). If \(P\) is nonempty, then there must exist a character \(d\) in the range \([l, r]\) such that \(P = d + sub\) (i.e. \(P[0] = d\) and \(P[1..|P|-1] = sub\)). If \(P\) is empty or if \(P[0]\) is not in the range \([l, r]\), then the substring does not qualify. It is guaranteed that \(1 \le x, y \le n\) and \(0 \le l \le r < m\), and \(k\) is a nonnegative integer less than the current operation number.
3. Operation 2: 2 x y. Replace the current state of the x-th string with the current state of the y-th string. It is guaranteed that \(1 \le x, y \le n\).
4. Operation 3: 3 s l r. You are given a string s. For each of the n current strings, count the number of substrings sub in that string satisfying: if \(s\) is nonempty and \(s[0]\) is within \([l, r]\), then \(s = d + sub\) for some \(d\) in \([l, r]\) (i.e. \(s[0] = d\) and \(s[1..|s|-1] = sub\)); otherwise, the count is 0. Output n numbers in one line corresponding to each string in order. It is guaranteed that \(0 \le l \le r < m\).

Note: The input file might be encrypted to force you to process the operations online. Make sure your solution processes the operations in the given order.

Observations: In operations 1 and 3, note that the condition is equivalent to requiring that the pattern (either the historical string for operation 1 or the given string \(s\) for operation 3) is of the form \(d + sub\) where \(d \in [l, r]\). Therefore, if the pattern is nonempty and \(d =\) the first character of the pattern is in the range \([l, r]\), then the problem reduces to counting the occurrences of the string pattern \(P[1..|P|-1]\) as a substring (with overlapping occurrences allowed) in the specified string(s).

inputFormat

The first line contains three integers: m n q.

The next n lines each contain a string representing the initial state of the i-th string (each character is a digit between 0 and m-1; the string may be empty).

Each of the following q lines represents an operation. The format for each operation is as follows:

• Operation 0: 0 x c
• Operation 1: 1 x y k l r
• Operation 2: 2 x y
• Operation 3: 3 s l r

For operations of type 1 and 3, you should output answers as described in the output section.

outputFormat

For each operation of type 1, output a single integer in a new line representing the count of substrings in string x (in its current state) that satisfy the condition with respect to the historical state of string y after operation k.

For each operation of type 3, output a single line containing n space-separated integers. The i-th number is the count of substrings in the i-th string (current state) that satisfy the condition with the given string s.

sample

10 2 5


0 1 3
0 2 1
1 1 2 0 3 5
2 1 2
3 31 3 5

0
1 1

</p>