Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Max Mex

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOnce Grisha found a tree (connected graph without cycles) with a root in node $$$1$$$.

But this tree was not just a tree. A permutation $$$p$$$ of integers from $$$0$$$ to $$$n - 1$$$ is written in nodes, a number $$$p_i$$$ is written in node $$$i$$$.

As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.

Let's define a function $$$MEX(S)$$$, where $$$S$$$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.

Let $$$l$$$ be a simple path in this tree. So let's define indices of nodes which lie on $$$l$$$ as $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$.

Define $$$V(l)$$$ as a set {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}.

Then queries are:

- For two nodes $$$i$$$ and $$$j$$$, swap $$$p_i$$$ and $$$p_j$$$.
- Find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of nodes of a tree.

The second line contains $$$n$$$ integers — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — the permutation $$$p$$$, it's guaranteed that all numbers are different .

The third line contains $$$n - 1$$$ integers — $$$d_2$$$, $$$d_3$$$, $$$\ldots$$$, $$$d_n$$$ ($$$1 \leq d_i < i$$$), where $$$d_i$$$ is a direct ancestor of node $$$i$$$ in a tree.

The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain the description of queries:

At the beginning of each of next $$$q$$$ lines, there is a single integer $$$t$$$ ($$$1$$$ or $$$2$$$) — the type of a query:

- If $$$t = 1$$$, the line also contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$) — the indices of nodes, where values of the permutation should be swapped.
- If $$$t = 2$$$, you need to find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Output

For each type 2 query print a single integer — the answer for this query.

Examples

Input

6 2 5 0 3 1 4 1 1 3 3 3 3 2 1 6 3 2

Output

3 2

Input

6 5 2 1 4 3 0 1 1 1 3 3 9 2 1 5 3 2 1 6 1 2 1 4 2 2 1 1 6 2

Output

3 2 4 4 2

Note

Number written in brackets is a permutation value of a node.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 20:33:42 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|