Given a tree where each edge has a character assigned to it. A constant $X$ is given.

There are two types of operations, each consisting of three integers and a string:

1 x y S: For 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$ from string $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 occurrences of $S$ in the string formed by the directed simple path from $x$ to $y$. (Matching here means: treating $S$ as a pattern string and matching it position by position along the string formed by the path.) For example, if $S=121$ and the string on the path is $1212122$, there are 2 matches, occurring at positions $[1,3]$ and $[3,5]$.

The indices of all strings $S$ mentioned above are 1-based, and it is guaranteed that the length of every input string $S$ is $X$.

Input

The first line contains three space-separated integers $n, m, X$.

The next line contains $n-1$ integers, where the $i$-th number represents the parent $f_{i+1}$ of node $i+1$. It is guaranteed that the parent's index is smaller than the node's index.

The next line contains $n-1$ characters, where the $i$-th character represents the character $a_{i+1}$ on the edge between node $i+1$ and its parent.

The next $m$ lines each contain three space-separated integers $opt, x, y$ and a string $S$ of length $X$, representing an operation.

Output

For each type 2 operation, output the answer on a new line.

Examples

Input 1

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

Output 1

1
1
1
0

Subtasks

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

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

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

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

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

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

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

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

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

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