Bajtosz has reached the final of the game show "One of n!". In this game, the contestant must guess a hidden permutation $p$ of the numbers $0, 1, 2, \dots, n - 1$. In each round, the contestant asks a question described by a permutation $q$ of the numbers $0, 1, 2, \dots, n - 1$ chosen by them, and two numbers $a, b \in \{0, 1, \dots, n - 1\}$. The host begins by determining the permutation $r$ which is the composition of permutation $q$ with permutation $p$. Thus, for every $i \in \{0, 1, \dots, n - 1\}$, in permutation $r$, the number $i$ maps to the number $q(p(i))$. Next, the host informs the contestant whether the numbers $a$ and $b$ are in the same cycle in permutation $r$. Formally, the cycle containing $a$ in permutation $r$ is the sequence $a, r(a), r(r(a)), r(r(r(a))), \dots$ (the sequence can be terminated when the number $a$ appears in it for the second time). We ask whether the number $b$ is present in such a sequence.

For example, consider the permutation $p = [3, 2, 1, 0, 4]$. This notation means that in permutation $p$, the number $0$ maps to $3$, $1$ to $2$, $2$ to $1$, $3$ to $0$, and $4$ to $4$. Applying the permutation $q = [2, 0, 4, 3, 1]$ to it, we obtain the permutation $r = [3, 4, 0, 2, 1]$, which is illustrated in the figure below.

The cycles of the resulting permutation $r$ look as shown in the figure below:

For example, the numbers $2$ and $3$ lie on the same cycle in permutation $r$, while $2$ and $4$ do not.

The contestant's goal is to guess the permutation $p$ using a limited number of queries. Help Bajtosz play in such a way as to win the highest possible prize in the game show.

Interaction

This is an interactive task. You must write a program that plays in the game show using the provided library. To use the library, include the following in your program:

• C++: #include "perlib.h"
• Python: from perlib import *

Your program will be compiled/run using the command:

• C++: g++ -O3 -static per.cpp perlib.cpp -std=c++20
• Python: python3 per.py

The following function returns the length of the permutation $n$ ($1 \le n \le 500$):

• C++: int daj_n()
• Python: daj_n() -> int

The next function returns the maximum number of queries $z$. If your program makes more queries, it will receive a Wrong Answer verdict.

• C++: int daj_z()
• Python: daj_z() -> int

The following function returns the subtask number (see the Scoring section). For the example test, its result is $1$.

• C++: int daj_podzadanie()
• Python: daj_podzadanie() -> int

You can use the following function to find out if $a$ and $b$ are on the same cycle in permutation $r$, which is the composition of permutation $q$ with the (unknown to you) permutation $p$. The result of the function is true (in C++) or True (in Python) if $a$ and $b$ are in the same cycle, and false (in C++) or False (in Python) otherwise.

• C++: bool zapytaj(std::vector<int> q, int a, int b)
• Python: zapytaj(q: list[int], a: int, b: int) -> bool

The last function provides the permutation $p$ as the answer.

• C++: void odpowiedz(std::vector<int> p)
• Python: odpowiedz(p: list[int]) -> None

In C++, this function terminates the program. In Python, this function does not terminate the program. The user should terminate the program immediately after calling this function.

The representation of permutations in the functions is as follows:

• C++: Permutations $q$ and $p$ are provided as function arguments in the form of vectors (std::vector) of length $n$. The number at position $i$ ($0 \le i < n$) should be equal to the number to which $i$ maps in the described permutation.
• Python: Permutations $q$ and $p$ are provided as lists of elements of type int of length $n$. The number at position $i$ ($0 \le i < n$) should be equal to the number to which $i$ maps in the described permutation. Do not pass generators or numpy arrays. A generator can be converted to a list using the list(variable) instruction.

Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but remember that this consumes valuable time.

Examples

Input 1

daj_n()
zapytaj({0,1,2,3,4}, 0, 1)
zapytaj({0,1,2,3,4}, 1, 2)
zapytaj({0,1,2,3,4}, 2, 3)
zapytaj({0,1,2,3,4}, 0, 3)
zapytaj({2,0,4,3,1}, 4, 1)
zapytaj({2,0,4,3,1}, 4, 0)
zapytaj({2,0,4,3,1}, 2, 4)
zapytaj({2,0,4,3,1}, 4, 3)
zapytaj({2,0,4,3,1}, 0, 3)
odpowiedz({3,2,1,0,4})

Output 1

5
false
true
false
true
true
false
false
false
true
-

Scoring

The test suite is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

The library sets the permutation $p$ at the very beginning and then answers subsequent questions.

Experiments

In the Files and tests section in SIO, you can find a sample implementation of the library and a sample test in the format accepted by this library.

The sample library reads $n$ and $z$ sequentially in the first line of input, and in the second line, $n$ numbers representing the successive values of the permutation $p$: $p(0), p(1), \dots, p(n - 1)$. The function daj_podzadanie() returns $-1$.

The implementation of the library used to evaluate your solutions may differ from the sample one.

Note: In this task, trial runs in SIO and the evaluation script on computers are not available.