You will be given a balanced binary tree of nodes. Each of the nodes of the tree will contain a non-negative integer value. Then, you will be asked to perform queries on the given tree. Each of the queries will be one of the two types described below.
This is the type of query. This query asks you to change the value of node to .
This is the type of query. This query asks you to print the MEX of all integers present in the subtree of node.
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.
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 .
The first line of the input will contain a positive integer which denotes the number of nodes in the tree. The nodes of the tree are numbered from to .
The next line will contain integers. The positive integer is the parent node of node. If the value is then the node is the root node of the tree.
Then, there will be a line containing positive integers. The positive integer is the value assigned to the node. All the values will be 32-bit non-negative integers.
The fourth line of the input will contain a positive integer which denotes the number of queries. Each of the next lines will contain one of the two types of queries described in the statement.
This is the type of query. This query asks you to change the value of node to . Here, and will be a 32-bit non-negative integer.
This is the type of query. This query asks you to print the MEX of all integers present in the subtree of node. Here, .
Print the MEX value for each type of query in a new line.
Input | Output |
---|---|
3 -1 1 1 0 1 2 5 2 1 2 2 2 3 1 1 3 2 1 | 3 0 0 0 |