This is an interactive problem.

You are obsessed with a puzzle game. In this level, your task is to open a treasure chest.

You have $n$ keys, numbered $0 \sim n-1$, and there are $n$ slots on the treasure chest, also numbered $0 \sim n-1$. Your task is to collect clues, insert the keys into the slots in a specific order, and then press a switch to open the chest. This correct key order can be viewed as a permutation $p$ of length $n$ (0-indexed), where $p_i$ represents the key that should be placed in slot $i$.

Your attempt can be viewed as providing a permutation $q$ of length $n$, representing that key $q_i$ is placed in slot $i$. If $p_i = q_i$ for every $0 \le i \le n-1$, your attempt is correct, you will open the chest, and successfully clear the level; otherwise, you fail. You only have one chance to attempt, so you must be extremely careful.

After careful observation, you discover the secret of the treasure chest: there is a hidden button on the back of the chest. After you provide a permutation $q$ and place the keys into the slots accordingly, you can press the hidden button, and the chest will tell you how many keys are placed in the correct position—that is, how many $0 \le i \le n-1$ satisfy $p_i = q_i$. This operation is called a query. You can change your permutation $q$ and perform queries multiple times before pressing the final opening switch, until you have collected enough information to determine the answer permutation $p$.

However, for the sake of game difficulty and fun, there is a special rule: the number of times you query the chest must not exceed $20,000$. Once it exceeds this limit, the chest will be permanently locked, meaning you have failed the game. Whether you succeed or not depends on your skills!

Implementation Details

You do not need to, and should not, implement the main function. You need to add #include "puzzle.h" at the beginning of your program and implement the following function:

void play(int n);

• $n$ represents the length of the permutation.
• During the execution of the interaction library, this function will be called exactly once.

You can call the following two functions:

int query(const std::vector<int> &q);

• $q$ should be a permutation of length $n$, meaning the length of $q$ should be $n$, and all integers from $0 \sim n-1$ must appear exactly once in $q_0 \sim q_{n-1}$.
• The function will compare the permutation $q$ you provided with the answer permutation $p$ and return the result of this query, i.e., how many integers $i$ satisfy $0 \leq i \leq n-1$ and $p_i = q_i$.
• The number of times you call this function should not exceed $20,000$.

void check(const std::vector<int> &q);

• $q$ should be a permutation of length $n$, meaning the size of $q$ should be $n$, and all integers from $0 \sim n-1$ must appear exactly once in $q_0 \sim q_{n-1}$.
• This function should be executed exactly once while your program is running the play function.
• The function will compare the permutation $q$ you provided with the answer permutation $p$. If $p=q$, your answer is considered correct; otherwise, it is considered incorrect.
• In any case, the interaction library will output the corresponding information and terminate immediately after executing this function.

You must ensure that the parameters passed when calling the query or check functions meet the above requirements.

You can view the reference interaction library in the provided files to learn more implementation details.

Testing Your Program

The provided files include a reference implementation of the interaction library, grader.cpp. The interaction library used for final testing is different from this implementation, so the contestant's solution should not rely on the implementation details of the interaction library.

Assuming your source file is named puzzle.cpp, you need to place the provided files in the same directory as your source file and use the following command to compile it into an executable:

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

When running the executable compiled by the method above:

• The executable will read data from standard input in the following format:

  • First line: a positive integer $n$, representing the length of the permutation. You must ensure $2 \leq n \leq 1000$;
  • Second line: $n$ integers $p_0, p_1, \dots, p_{n-1}$, representing the answer permutation. You must ensure $p_0, \dots, p_{n-1}$ is a permutation of length $n$, meaning all integers from $0 \sim n-1$ appear exactly once.

• After reading is complete, the interaction library will test using this set of data and output the following:

  • If your program runs normally, the number of calls to the query function does not exceed $20,000$, and the correct permutation is passed when calling the check function, it will output:

    Correct.
    cnt = x

    where $x$ is the number of times your program called the query function.

  • Otherwise, it will output the corresponding error message.

Examples

Input 1

3
1 0 2

Output 1

Correct.
cnt = 3

Note 1

This is a possible output file obtained using the provided grader.cpp and a correctly running source program.

For this example, one possible sequence of calls is:

• Call query([0, 1, 2]), returns $1$;
• Call query([0, 2, 1]), returns $0$;
• Call query([1, 0, 2]), returns $3$;
• Call check([1, 0, 2]).

Subtasks

This problem uses bundled testing. For each subtask, your score is the minimum score of all test cases in that subtask.

For all test cases, $1 \leq n \leq 1000$.

For the first 6 subtasks, if your program runs normally, calls the query function no more than $20,000$ times, and passes the correct permutation to the check function, you can receive full marks for that test case.

For the 7th subtask, your program may receive partial points in addition to the above. Let $m$ be the number of times your program calls query. Your score is as follows:

Note

It is guaranteed that for any valid data and calls within the limits, the interaction library itself will not take more than $0.2\text{s}$ to run and will not use more than $128\text{MiB}$ of memory.

The header files required for the interaction library to run normally are already provided in the reference interaction library; your program can include any header files you need.

The interaction library for this problem is not adaptive, meaning the answer permutation is determined before the play function is called and will not change based on your queries.

Gaining points by accessing input/output files, attacking the judging system, or attacking the judging library is considered cheating, and the resulting scores will be invalid.