ydc loves strings and has a unique perspective on them.

Strings are composed of characters. There are $m$ types of characters, numbered $0, \dots, m-1$.

For integers $l, r$, two strings $s$ and $t$ are said to be equal via $[l, r]$ if $s$ becomes equal to $t$ after prepending a character with a value in the range $[l, r]$ to $s$.

ydc gives you $n$ strings, numbered $1, \dots, n$, and requires you to perform $q$ operations. Each operation is one of the following four types:

• Operation 0: Append a character $c$ to the $x$-th string. It is guaranteed that $1 \leq x \leq n$ and $0 \leq c < m$.
• Operation 1: Query how many substrings of the current $x$-th string are equal via $[l, r]$ to the $y$-th string as it existed after the $k$-th operation. $k$ is a non-negative integer less than the current operation index, where $k = 0$ represents the state before any operations. It is guaranteed that $1 \leq x, y \leq n$ and $0 \leq l \leq r < m$.
• Operation 2: Replace the $x$-th string with the $y$-th string. It is guaranteed that $1 \leq x, y \leq n$.
• Operation 3: Given a string $s$, for each of the $n$ strings, query how many substrings are equal via $[l, r]$ to $s$, where $0 \leq l \leq r < m$.

Additionally, the input file may be encrypted to force you to perform operations online.

Input

The first line contains three integers $n, m, \mathrm{ty}$, representing the number of strings, the size of the character set, and whether the data is encrypted, respectively. If the data is encrypted, $\mathrm{ty}$ is $1$; otherwise, it is $0$.

If the data is encrypted, let $\mathrm{lastans}$ be the last output value before the current operation (if no output has been produced yet, $\mathrm{lastans} = 0$). All numbers read in the current operation are encrypted as the original value XORed with $\mathrm{lastans}$.

Strings are given in the following format: the first number is a positive integer $l$ representing the length of the string, followed by $l$ integers separated by spaces, representing the character value at each position.

The next $n$ lines provide the $n$ initial strings.

Then, read a positive integer $q$, the number of operations.

The following $q$ lines each contain information about an operation. The first number in each line is the operation type.

If it is operation 0, it is followed by two integers $x, c$.

If it is operation 1, it is followed by five integers $x, y, k, l, r$.

If it is operation 2, it is followed by two integers $x, y$.

If it is operation 3, it is followed by two integers $l, r$ and a string $s$.

Output

Answer the queries in the order they appear in the input.

For each operation 1, output one integer per line representing the answer.

For each operation 3, output $n$ integers on one line, representing the number of substrings satisfying the condition for each string, respectively.

Examples

Input 1

3 3 0
5 0 1 1 1 2
1 1
2 1 1
4
0 1 1
3 0 1 1 1
2 2 1
1 1 2 0 0 1

Output 1

3 0 1
3

Input 2

3 3 1
5 0 1 1 1 2
1 1
2 1 1
4
0 1 1
3 0 1 1 1
3 3 0
0 0 3 1 1 0

Output 2

3 0 1
3

Constraints

$2 \leq n \leq 5$, $1 \leq m \leq 10^5$, $1 \leq q \leq 2 \times 10^5$.

The total length of the initial $n$ strings does not exceed $2 \times 10^5 + 20$.

The total length of strings read in operation 3 does not exceed $10^6$.

The data is guaranteed to be valid.

It is guaranteed that there exists a string of length at most $4 \times 10^5$ such that the $n$ strings are substrings of it at any time.

For the first 30% of the data, $q \leq 1000$, the total length of the initial $n$ strings does not exceed $1000 + 20$, and the total length of strings read in operation 3 does not exceed $10^4$.

For the first 60% of the data, it is guaranteed that all $l=0$ and $r=m-1$.

For the first 80% of the data, it is guaranteed that the data is not encrypted.