This is an interactive problem.

On the eve of the dessert festival's opening, the head chef is carefully crafting the shop's signature creation, “千层幻彩慕斯”. This dessert consists of $n$ pieces of mousse with different flavors, numbered $0,1,\dots,n-1$ in order.

However, in the rush, the assistant accidentally mixed up the order of the mousse pieces. They are now arranged in a row from left to right, forming an unknown positional permutation $p=(p_0,p_1,\dots,p_{n-1})$, where $p_i$ is the number of the mousse piece at position $i$.

To determine the exact position of each piece of mousse, you can use a dessert tester. Each time you choose three pairwise distinct positions $x,y,z$, the tester returns the sum of the smallest and largest numbers among these three mousse pieces:

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

The opening bells are about to ring. Can you accurately reconstruct the true position of every piece of mousse using a limited number of tests?

There is a permutation $p$ of length $n$ whose elements are exactly $0,1,\ldots,n-1$. You do not know the contents of $p$.

You can choose three pairwise distinct indices $x,y,z$, and the grader will return

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

Your task is to reconstruct the entire permutation. The query limits and the method of calculating scores based on the number of queries are given below.

Implementation Details

You do not need to, and should not, implement the main function. Your submitted source file should contain:

#include "mousse.h"

You need to implement the following two functions:

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ is the subtask number; $c=0$ denotes the example. Each test case contains exactly one instance. For that test case, the grader calls init(c) once, followed by mousse(c,n) once.
• mousse should return an array of length $n$, with its $i$-th element equal to $p_i$. Indices start at $0$.

You can call the following function to make a query:

int query(int x, int y, int z);

You must satisfy $0\le x,y,z < n$, and $x,y,z$ must be pairwise distinct. The function returns $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.

Testing Your Program

The attachments contain mousse.h, the local grader grader.cpp, and an example program template_mousse.cpp. Save your own program as mousse.cpp; you can run the following commands in the directory for this problem:

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

The local grader reads the hidden permutation from standard input. Your program must not read these data itself. The input format is as follows:

• The first line contains two integers $c,n$.
• The second line contains $p_0,p_1,\ldots,p_{n-1}$.

If the answer is correct, the grader outputs Correct! and Max queries used: Q, where $Q$ is the number of queries for that test case; if the answer is incorrect, it outputs Wrong answer.. If an invalid query is made or the query limit is exceeded, the program prints an error message to standard error and exits. You can add the -v option to see the number of queries for that test case.

Examples

Input 1

0 10
0 2 9 1 5 8 3 7 6 4

Output 1

Correct!
Max queries used: 15

Note

For example, when query(0,1,2) is called, the three corresponding values are $0,2,9$, and it returns $0+9=9$. The reference program uses $15$ queries on this instance. This number may differ if you use another strategy.

Constraints

For all test data, $n\in\{10,100,10^5\}$, and $p$ is a permutation of $0\sim n-1$. Each test case contains exactly one instance.

For the example, $c=0$, $n=10$, and the query limit is $1000$.

Subtasks

Note:

• The grader is non-adaptive. The permutation for each test case is fixed before your program is called and does not change in response to queries.
• You must not obtain the hidden permutation by reading standard input or by any other prohibited means. The implementation of the grader used in the final evaluation may differ from that of the local grader.

If, in a test case, mousse returns an incorrect answer, the arguments to query are invalid, or the number of queries exceeds the subtask's $Q_{\max}$, the score multiplier for that test case is $0$.

For subtasks $1,2$, you receive the full score for the subtask only if all test cases are correct.

For subtasks $3,4$, if the score multiplier for any test case is $0$, the subtask receives $0$ points. Otherwise, let $Q$ be the maximum number of queries across all test cases in that subtask. The score multiplier $f(Q)$ is determined by the following table:

If $Q\le 99970$, then $f(Q)=100\%$. If $Q$ lies between two adjacent rows $(Q_i,f_i)$ and $(Q_{i+1},f_{i+1})$ in the table, then:

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

The score for subtask $3$ is $30f(Q)$, and the score for subtask $4$ is $60f(Q)$. The final score is rounded to $3$ decimal places.

Time limit: $10\ \mathrm{s}$.

Memory limit: $512\ \mathrm{MiB}$.