This is an interactive problem.

As a skilled OI contestant, you are already well-versed in various data structure problems and can easily solve them during competitions. One day, you open an OJ and see this problem:

Given a rooted tree with $n$ nodes, labeled $1, 2, \cdots, n$, where $1$ is the root. Each edge has a distinct weight between $1$ and $n - 1$. Maintain a data structure that supports swapping the weights of edges with weights $x$ and $y$, and querying the maximum weight of all edges on the path from the root to node $u$.

Such a simple and classic tree problem is no challenge for you. Tired of maintaining updates and answering queries, you decide to switch roles. This time, you are the one asking the questions, and you need to construct appropriate operations to extract the problem's data.

Specifically, you do not know the structure of the tree or the initial weight of each edge. You need to obtain the tree structure and the initial weight of each edge on the tree through the following two operations:

1. Given positive integers $x, y$, where $1 \le x, y < n, x \neq y$, swap the weights of the two edges with weights $x$ and $y$.
2. Given a positive integer $u$, where $2 \le u \le n$, obtain the maximum weight among all edges on the path from node $1$ to node $u$.

The problem guarantees that the tree structure and the weight of each edge are predetermined and will not be generated dynamically based on your operations.

Implementation Details

You need to include the header file #include "ds.h". You can call the following functions to interact with the interactor:

void exchange(int x, int y);

• This function corresponds to operation $1$, which swaps the weights of the two edges with weights $x$ and $y$.
• You must ensure $1 \le x, y < n, x \neq y$.

int query(int u);

• This function corresponds to operation $2$, returning the maximum weight of all edges on the path from node $1$ to node $u$.
• You must ensure $2 \le u \le n$.

void answer(std::vector<int> par, std::vector<int> val);

• This function is used to provide your answer, formatted as follows:
  • par is an array of length $n - 1$, where par[i] represents the parent of node $i + 2$ in the tree, for $0 \le i \le n - 2$.
  • val is an array of length $n - 1$, where val[i] represents the initial weight of the edge connecting node $i + 2$ to its parent, for $0 \le i \le n - 2$.
• You must call this function exactly once!

You do not need to, and should not, implement a main function. In this problem, you only need to implement the following function:

void solve(int n, int lim1, int lim2);

• Here, $n$ is the number of nodes in the tree, $lim1$ is the limit on the number of operations of type $1$, and $lim2$ is the limit on the number of operations of type $2$.
• During final testing, for each test case, the interactor will call the solve function exactly once, and score based on the correctness of the answer function call.

In the problem attachment, we provide sample.cpp for your reference, which you can use as a basis for your program.

Testing Your Program

The file grader.cpp is provided in the problem directory. The final interactor used for testing differs from the provided one, so your implementation should not rely on the specific implementation of the interactor.

You need to place your program ds.cpp, grader.cpp, and ds.h in the same directory and use the following compilation command to generate the executable ds(.exe):

g++ -o ds ds.cpp grader.cpp -O2 -std=c++14 -lm

The problem attachment also provides compile.sh, which contains this compilation command. You can run it to compile, or copy the command from the file.

The executable reads data from standard input in the following format:

• The first line contains three positive integers $n, lim1, lim2$, representing the number of nodes, the limit for operation $1$, and the limit for operation $2$. The interactor is guaranteed to handle cases where $2 \le n \le 500000$; no correctness is guaranteed for $n > 500000$.
• The second line contains $n - 1$ positive integers $p_2, p_3, \cdots, p_n$, where $p_i$ is the parent of node $i$. You must ensure $1 \le p_i \le n$ and that the input provides a valid tree structure.
• The third line contains $n - 1$ positive integers $v_2, v_3, \cdots, v_n$, where $v_i$ is the weight of the edge connecting $i$ to $p_i$. You must ensure $v_2, v_3, \cdots, v_n$ form a permutation of $1$ to $n - 1$.
• When testing locally, please ensure your input format meets the requirements; otherwise, we do not guarantee the interactor will function correctly.

If your input is valid and there are no runtime errors, the provided interactor will output information based on your calls:

• If an exchange call violates $1 \le x, y < n, x \neq y$, it outputs: Invalid call of exchange(x, y)!.
• If the number of exchange calls exceeds $lim1$, it outputs: Too many exchanges!.
• If a query call violates $2 \le u \le n$, it outputs: Invalid call of query(u)!.
• If the number of query calls exceeds $lim2$, it outputs: Too many queries!.
• The interactor terminates immediately after outputting any of the above error messages.
• The interactor will output a hint every time you call the answer function:
  • If the length of par or val is not $n - 1$, it outputs Invalid output!.
  • If the par array does not match the tree structure, it provides the first incorrect position: The answer to p[i] is wrong! The right answer is j, but you output k., where $2 \le i \le n$, $j = p_i$ is the true parent, and $k = \text{par}[i - 2]$ is your output.
  • If the par array is correct but the val array does not match the initial edge weights, it provides the first incorrect position: The answer to v[i] is wrong! The right answer is j, but you output k., where $2 \le i \le n$, $j = v_i$ is the true initial weight, and $k = \text{val}[i - 2]$ is your output.
  • If both par and val are correct, it outputs the number of calls: Right output! cnt1 = A, cnt2= B., where $A$ is the number of exchange calls and $B$ is the number of query calls.
• You may call answer multiple times to test your program with the provided interactor. However, for your submitted code, calling answer more than once will result in a score of 0.

Your program should not interact with standard input or output, otherwise it will be considered an attack on the interactor.

Examples

Input 1

3 100 100
1 2
2 1

Output 1

Right output! cnt1 = 2, cnt2 = 5.

Note 1

A possible input is as follows: The parent of node $2$ is $1$, and the initial weight of the edge $(1, 2)$ is $2$. The parent of node $3$ is $2$, and the initial weight of the edge $(2, 3)$ is $1$.

A possible interaction process: Call query(2), returns $2$. Call exchange(1, 2). Now, the weight of edge $(1, 2)$ is $1$, and the weight of edge $(2, 3)$ is $2$. Call query(2), returns $1$. Now we know $1$ and $2$ are directly connected. Call query(3), returns $2$. Call exchange(1, 2). Call query(3), returns $2$. Now we can deduce $2$ and $3$ are directly connected. Call query(2), returns $2$. Now we can deduce that after two exchange operations, the weight of edge $(1, 2)$ is $2$ and the weight of edge $(2, 3)$ is $1$. Call answer([1, 2], [2, 1]), terminate.

Subtasks

Special Property A: Each node has at most $1$ child (the tree is a chain). The labels of non-root nodes are uniformly randomly distributed. * The edge weight permutation is chosen uniformly at random from all $(n - 1)!$ possibilities.

Special Property B: The tree structure is generated randomly: For each $2 \le i \le n$, the parent of $i$ is chosen uniformly at random from $[1, i - 1]$. The labels of non-root nodes are then randomly shuffled. The edge weight permutation is chosen uniformly at random from all $(n - 1)!$ possibilities.

You can determine the special properties of the test data based on the values of $lim1$ and $lim2$.

Scoring

This problem is subject to the same constraints as traditional problems. For example, compilation errors result in 0 points, and runtime errors, time limit exceeded, or memory limit exceeded result in 0 points for the corresponding test case. You may only access variables you have defined and those provided by the interactor; accessing other memory may lead to errors.

Under these conditions, you receive points for a test case if and only if every function call has the correct parameter format, the number of exchange calls does not exceed $lim1$, the number of query calls does not exceed $lim2$, and the first call to answer provides the correct par and val arrays.

It is guaranteed that in both the provided and final evaluators, the worst-case complexity of exchange and query is $O(\log n)$. You have 4 seconds and 768 MB of memory available.

Note

We remind you again: The tree structure and the weight of each edge are predetermined and will not be generated dynamically based on your operations.

Pay attention to the time and memory consumption of your program.

Any attempt to access input/output files, attack the evaluation system, or attack the interactor is considered cheating, and the score will be invalid.