Given a tree with $n$ nodes, each node $i$ has a weight $a_i$.

A maximal monochromatic connected component containing a node $x$ is defined as a maximal set of nodes $S$ such that $x \in S$, and for any two nodes $i, j \in S$, there exists a sequence of nodes $p_1, p_2, \dots, p_t$ such that $p_1 = i$, $p_t = j$, and for every integer $k \in [1, t)$, $p_k$ and $p_{k+1}$ are adjacent in the tree, $a_{p_k} = a_{p_{k+1}}$, and $p_k \in S$.

There are $m$ operations:

• 1 x y: Given a node $x$, change the weight of every node in the maximal monochromatic connected component containing $x$ to $y$.
• 2 x: Given a node $x$, query the size of the maximal monochromatic connected component containing $x$.

Input

The first line contains two integers $n$ and $m$.

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

The third line contains $n$ integers, where the $i$-th integer represents $a_i$.

The following $m$ lines each contain an operation of the form 1 x y or 2 x, as described above.

Output

For each operation of type 2, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

2
4

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $20\%$ of the data, $n, m \leq 2 \times 10^3$.

For $40\%$ of the data, $n, m \leq 2 \times 10^5$.

For another $30\%$ of the data, $1 \le a_i, y \le 2$.

For $100\%$ of the data, $1 \le n, m, a_i, x, y \le 10^6$.