There are $n$ students forming a rooted tree, and each student has a $\text{gpa}$.

A student's major is defined as the connected component containing that student when only edges connecting two students with the same $\text{gpa}$ are kept.

The resentment value of a major is defined as $\max(dep[a] - dep[b] + 1)$ such that $a$ and $b$ are students in the major, where $dep_{root} = 0$ and $dep_{w} = dep_{parent(w)} + 1$.

Operation 1: Given $x$ and $y$, change the $\text{gpa}$ of student $x$ to $y$.

Operation 2: Given $x$ and $y$, change the $\text{gpa}$ of all students in the major containing student $x$ to $y$.

Operation 3: Given $x$, query the $\text{gpa}$ of student $x$, the number of students in the major containing $x$, and the resentment value of the major containing $x$.

Input

The first line contains an integer $n$.

The second line contains $n$ integers representing the parent of each node, where the $i$-th number is $< i$, and the parent of node $1$ is $0$.

The third line contains $n$ integers representing the $\text{gpa}$ of each student.

The fourth line contains an integer $m$.

The following $m$ lines each contain two or three integers representing an operation, with types as described above.

Output

For each type 3 operation, output a single line containing three integers separated by spaces, representing: the $\text{gpa}$ of student $x$, the number of students in the major containing $x$, and the resentment value of the major containing $x$.

Examples

Input 1

10
0 1 1 1 3 4 2 4 2 3
16 20 29 16 23 6 29 21 1 22
10
3 4
3 4
2 6 20
2 1 8
2 2 8
1 9 21
3 6
3 2
1 3 11
1 4 17

Output 1

16 2 2
16 2 2
20 1 1
8 3 2

Note

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

There are $c$ distinct $\text{gpa}$ values.

For $40\%$ of the data, $n, m \le 1000$.

For another $40\%$ of the data, $n, m \le 10^5$, $c = 2$, and the $\text{gpa}$ values are in the range $[1, 2]$.

For $100\%$ of the data, $n, m \le 10^5$, $c = 30$, and the $\text{gpa}$ values are in the range $[1, 30]$.