k-th ancestor

Input

The first line contain an integer $t$ (1 \le t \le 3) denoting the number of test cases. $t$ test cases follow. First line of each test case contains an integer $p$ (1 \le p \le 10^5), the number of nodes in the tree. $p$ lines follows each containing two integers $x$ and $y$ separated by a single space denoting $y$ as the parent of $x$. If $y$ is $0$, then $x$ is the root node of the tree. ($0$ is for namesake and is not in the tree). It is known that 1 \le x, y \le 10^5.

The next line contains an integer $q$ (1 \le q \le 10^5), the number of queries. $q$ lines follow each containing a query.

- $0$ $y$ $x$: $x$ is added as a new leaf node whose parent is $y$. $x$ is not in the tree while $y$ is in. - $1$ $x$: This tells that leaf node $x$ is removed from the tree. $x$ is a leaf in the tree. - $2$ $x$ $k$: In this query output the $k$-th (1 \le k \le 10^5) parent of $x$. $x$ is a node in the tree.

Output

For each query of type $2$, output the $k$-th parent of $x$. If $k$-th parent doesn't exist, output $0$ and if the node doesn't exist, output $0$.

Examples