Problem Description

Given a tree, each edge of the tree has a character on it. A constant $X$ is given.

There are two types of operations. Each operation inputs three integers and a string:

1 x y S: For the edges on the directed simple path from $x$ to $y$, replace the character on the $i$-th edge of the path with the corresponding character $S_i$ in $S$. It is guaranteed that the number of edges on the path from $x$ to $y$ is $X$.

2 x y S: Query the number of matches of $S$ on the string formed by the directed simple path from $x$ to $y$ (here, matching means: treat $S$ as the pattern string and match it against the path string position by position). For example, if $S = 121$ and the path string is $1212122$, then it matches 2 times, at positions $[1,3]$ and $[3,5]$.

For all strings $S$ above, indices start from $1$. It is guaranteed that the length of every input string is $X$.

Input Format

The first line contains three integers $n, m, X$ separated by spaces.

The next line contains $n - 1$ integers. The $i$-th integer denotes the parent $f_{i+1}$ of node $i+1$. It is guaranteed that the parent index of each node is smaller than the node index.

The next line contains $n - 1$ characters. The $i$-th character denotes the character $a_{i+1}$ on the edge from node $i+1$ to its parent.

Then follow $m$ lines. Each line contains three integers $opt, x, y$ separated by spaces and a string $S$ of length $X$, representing one operation.

Output Format

Output a total of $m$ lines. Each line contains one integer, representing the answer to each operation of type $2$.

10 7 2
1 2 3 2 3 3 3 3 7
212111121
2 1 4 21
1 10 3 21
1 9 7 22
2 2 10 12
2 6 8 11
1 9 8 12
2 4 7 11

1
1
1
0

Hint

Idea: nzhtl1477, Solution: ComeIntoPower&nzhtl1477&ccz181078, Code: ccz181078, Data: ccz181078.

Constraints:

For $10\%$ of the testdata, $1 \le n, m \le 250$.

For another $10\%$ of the testdata, there are no type $1$ operations.

For another $10\%$ of the testdata, $X = 1$.

For another $10\%$ of the testdata, $X \le 3$.

For another $10\%$ of the testdata, $X \ge 20000$.

For another $10\%$ of the testdata, $f_i = i - 1$.

For another $10\%$ of the testdata, $a_i \le 1$.

For another $10\%$ of the testdata, $1 \le n, m \le 2.5 \times 10^4$, and $mX \le 2.5 \times 10^4$.

For another $10\%$ of the testdata, $1 \le n, m \le 2.5 \times 10^5$, and $mX \le 2.5 \times 10^5$.

For $100\%$ of the testdata, $1 \le n, m, X \le 5 \times 10^5$. The alphabet consists of integers in $[1,9]$, and $mX \le 5 \times 10^5$.

Translated by ChatGPT 5