At the pinnacle of human wisdom stands a supercomputer with a word length of $1048576$ bits. The renowned theoretical computer scientist Dr. P is using it for various research projects. Unfortunately, a typhoon cut off the power supply, leaving the supercomputer inoperable. Since Dr. P must submit his experimental results tomorrow, he has to turn to you, someone who has studied informatics, for help.

This is an interactive problem.

Dr. P has abstracted his computational task into operations on an integer. Specifically, there is an integer $x$, which is initially $0$.

Dr. P's goal is to crack an encryption machine that can perform operations on $x$. The machine contains $n$ non-negative integers $p_0, p_1, \cdots, p_{n-1}$, where $\{p_i\}$ is a permutation of $\{0, 1, \dots, n-1\}$.

The machine has $n$ buttons, numbered $0, 1, \dots, n-1$. Operating the $i$-th button adds $2^{p_i}$ to $x$, and the machine then outputs $popcount(x)$, which is the number of $1$s in the binary representation of $x$.

You need to help Dr. P recover the permutation $p$ inside the machine.

Notably, the permutation $p$ is determined before the program runs and does not change dynamically based on the user's queries.

Implementation

You need to include the header file integer.h.

You do not need to, and should not, implement the main function. The interface of the function you need to implement is as follows:

std::vector<int> findPermutation(int n);

This function should return an array of length $n$ representing the permutation you recovered.

The interface of the function you can call is as follows:

int operate(const int i);

This function accepts an integer $i$ in the range $[0, n)$, representing the index of the button you are operating.

Calling this function returns a positive integer representing the $popcount$ of $x$ after the operation.

The provided files include a sample contestant file template_integer.cpp, which you can copy, rename to integer.cpp, and use for your implementation.

Local Testing

The provided files include two interaction library files, integer.h and grader.cpp, which are our reference implementations of the interaction library. The interaction library used for final evaluation may differ slightly, so your solution should not rely on the specific implementation of this library.

Please name your program integer.cpp, place it in the same directory as the interaction library files, and use the following command to compile it into an executable named integer:

g++ grader.cpp integer.cpp -o integer -O2 -std=c++11

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

The first line contains a positive integer $n$.

The second line contains a permutation $p_0, p_1, \dots, p_{n-1}$.

After reading the input, the interaction library will call findPermutation once and test whether your program returns the correct answer.

If your program completes the operation correctly, it will output the number of operate calls and your score for this test case, and the program will exit with a return value of $0$.

Otherwise, it will output the first error encountered, and the program will exit with a return value of $-1$.

Scoring

Attacking the interaction library in any form is strictly prohibited.

If your program does not complete the operation correctly, you will receive $0$ points for that test case.

Otherwise, let $x$ be the number of times your program calls operate. Your score ratio $s$ for a test case is calculated as follows:

$$\begin{equation}s= \begin{cases} 1 & x < 8 \times 10^5\\ \frac{8 \times 10^5}{x} & 8 \times 10^5 \leq x \leq 2 \times 10^6 \\ \max(\frac{180-20\lg {5x}}{100},0) & x > 2 \times 10^6 \end{cases} \end{equation}$$

Note that if the number of interactions exceeds $2 \times 10^8$, your program will receive $0$ points. Exceeding this number of interactions may lead to TLE or other unpredictable evaluation results.

We guarantee that the interaction library will consume at most $2$ seconds and $64$ MB of memory during these $2 \times 10^8$ operations.

Your score for a subtask is the full score of that subtask multiplied by the minimum score ratio you obtained across all test cases in that subtask (including all test cases in all subtasks it depends on).

Examples

Assume the input data is:

4
0 3 1 2

The following is a possible interaction process:

• $operate(0)$: $x=1_{(2)}$, returns $1$.
• $operate(2)$: $x=11_{(2)}$, returns $2$.
• $operate(0)$: $x=100_{(2)}$, returns $1$, implying $p_0+1=p_2$.
• $operate(3)$: $x=1000_{(2)}$, returns $1$, implying $p_2+1=p_3$.
• $operate(1)$: $x=10000_{(2)}$, returns $1$, implying $p_3+1=p_1$.

At this point, we have determined the permutation $p$ and exit findPermutation, returning $\{0, 3, 1, 2\}$.

Subtasks

For all data, $1 \le n \le 5\,000$.

Subtask #1 ($5$ points): $n \le 10$.

Subtask #2 ($10$ points): $n \le 70$.

Subtask #3 ($15$ points): $n \le 900$.

Subtask #4 ($10$ points): $p_0=0$.

Subtask #5 ($60$ points): No special restrictions.

Additionally, if the constraints of subtask $x$ are not weaker than those of subtask $y$, subtask $x$ depends on subtask $y$.