Each node $i$ has associated tuple information $(a_i, b_i)$.
Given a tree of size $n$. Initially, all nodes are $(0, 0)$. The root is $1$.
Given $m$ operations:
- $1 \ x \ c$: Let the current operation index be $z$. For all nodes $i$ on the path from $x$ to the root, if $a_i = c$, update $(a_i, b_i) \leftarrow (c, b_i)$; otherwise, update $(a_i, b_i) \leftarrow (c, z)$.
- $2 \ x$: Query $(a_x, b_x)$.
Input
The first line contains two integers $n$ and $m$, representing the size of the tree and the number of operations.
The next line contains $n - 1$ integers, where the $i$-th integer $p_i$ represents the parent of node $i + 1$.
The next $m$ lines each contain either two or three integers representing the operations.
Output
For each query, output two integers on a single line representing the answer.
Examples
Input 1
5 5 1 2 2 3 2 3 1 4 3 2 3 2 4 2 1
Output 1
0 0 0 0 3 2 3 2
Subtasks
Idea: FutaRimeWoawaSete, Solution: FutaRimeWoawaSete, Code: FutaRimeWoawaSete, Data: FutaRimeWoawaSete
| Test Case | $n$ | $m$ | Special Property |
|---|---|---|---|
| $1 \sim 5$ | $\leq 10^5$ | $\leq 10^5$ | $A$ |
| $6 \sim 10$ | $B$ | ||
| $11 \sim 15$ | $C$ | ||
| $16 \sim 20$ | $\leq 10^6$ | $\leq 10^6$ | $/$ |
Special Property $A$: $p_i$ is chosen uniformly at random from $[1, i - 1]$.
Special Property $B$: It is guaranteed that in all type $1$ operations, $c = 1$.
Special Property $C$: It is guaranteed that $p_i = i - 1$.
All data guarantees $n, q \leq 10^6, x, c \in [1, n]$.
It is guaranteed that examples $2, 3, 4, 5$ correspond to the properties of test cases $1 \sim 5, 6 \sim 10, 11 \sim 15, 16 \sim 20$ respectively and are generated using the same construction method.