Subtree MEX

You will be given a balanced binary tree of $N$ nodes. Each of the nodes of the tree will contain a non-negative integer value. Then, you will be asked to perform $Q$ queries on the given tree. Each of the queries will be one of the two types described below.

• $1$ $K$ $X$
  This is the $1{st}$ type of query. This query asks you to change the value of $K^{th}$ node to $X$.

• $2$ $I$
  This is the $2^{nd}$ type of query. This query asks you to print the MEX of all integers present in the subtree of $I^{th}$ node.

$\textbf{\underline{Definition}}:$

• ${MEX}:$ In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.

• $Balanced$ $Binary$ $Tree:$A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than $1$.

Input

The first line of the input will contain a positive integer $N$ $(1 \leq N \leq 10^{5})$ which denotes the number of nodes in the tree. The nodes of the tree are numbered from $1$ to $N$.

The next line will contain $N$ integers. The $i^{th}$ positive integer is the parent node of $i^{th}$ node. If the value is $-1$ then the $i^{th}$ node is the root node of the tree.

Then, there will be a line containing $N$ positive integers. The $j^{th}$ positive integer is the value assigned to the $j^{th}$ node. All the values will be 32-bit non-negative integers.

The fourth line of the input will contain a positive integer $Q$ $(1 \leq Q \leq 3 \times 10^{5})$ which denotes the number of queries. Each of the next $Q$ lines will contain one of the two types of queries described in the statement.

• $1$ $K$ $X$
  This is the $1{st}$ type of query. This query asks you to change the value of $K^{th}$ node to $X$. Here, $(1 \leq K \leq N)$ and $X$ will be a 32-bit non-negative integer.

• $2$ $I$
  This is the $2^{nd}$ type of query. This query asks you to print the MEX of all integers present in the subtree of $I^{th}$ node. Here, $(1 \leq I \leq 10^{5})$.

Output

Print the MEX value for each $2^{nd}$ type of query in a new line.

Sample

3
-1 1 1
0 1 2
5
2 1
2 2
2 3
1 1 3
2 1

3
0
0
0