Problem Type: INTERACTIVE(STANDARD SOLUTIONS WILL NOT WORK)

There are many legends concerning the Leaning Tower of Toruń. The wall of the tower is a circle with N ≥ 3 evenly spaced doors (in other words, the doors are the vertices of a regular N-gon). The doors are numbered from 0 to N−1, but in a random order. Please refer to the scoring section for more details about this.

One of the less known legends describes how every new inhabitant of the tower had to complete a certain challenge. The goal of the challenge was to list the doors, starting with some door and then walking around the circle (clockwise or counterclockwise), visiting each door exactly once.

This needs to be done without actually seeing the tower. Instead, the new inhabitant can ask questions of the following form: “Given three distinct doors x, y, z, which pairs of doors are the closest to each other: {x, y}, {y, z}, or {z, x}?”. The answer to such a question are all pairs (among {x, y}, {y, z} and {z, x}) of doors with the smallest Euclidean distance. The distance is simply the length of the shortest segment connecting the doors. Your task is to write a program that will ask a small number of such questions to determine the order
of the doors.

Interaction

This is an interactive task. You should write a program which finds a correct solution to the task and communicates with the interactor by reading from the standard input and writing to the standard output.

At the beginning of the interaction, your program should read two integers k and n (k = 12000, n = 500) from the standard input, denoting the maximum allowed number of queries and the number of doors in the tower respectively. 

Then your program should ask the questions in the following way:

• Your program should write a single line in the form of

? x y z

to the standard output, where x, y, and z are distinct integers (0 ≤ x, y, z ≤ n−1). This line represents a single question concerning doors x, y, and z.

• The response will be given as:

r
a1 b1
. . .
ar br

where r is an integer (1 ≤ r ≤ 3) representing the number of pairs of doors with the smallest distance.
Each such pair is described by two integers ai and bi (ai, bi ∈ {x, y, z} and ai < bi).
Once you have determined the order of the doors, you should write a single line in the form of

! x0 x1 . . . xn−1

to the standard output, where x0, x1, . . . , xn−1 is the order of the doors as described in the task statement.
Please note that there are exactly 2n possible correct answers since you can output the order starting from any door and then going in either direction. Any of them will be accepted.

Keep in mind that after each query or answer you have to flush the output buffer using
cout.flush() (or fflush(stdout) if using printf) in C++ or sys.stdout.flush() in Python. Otherwise your program may receive a Time Limit Exceeded verdict.

After writing the answer to the interactor, your program should immediately end the interaction.

Your program cannot open any files or use any other resources.

Please also note that the interactor is not adaptive, meaning that the initial order of the doors is fixed beforehand in each test case and does not change during the interaction.

Example interaction

Suppose we have one test case with n = 6, and the order of the doors is 5, 3, 0, 2, 1, 4. The interaction could look as follows:

Interactor
100 6

Comment
k = 100 and n = 6.

Your program
? 0 1 2

Comment
Your program asks which pairs of doors are the closest.

Interactor
2
0 2
1 2

Comment
Pairs of doors {0, 2} and {1, 2} are the closest.

Your program
? 4 1 3

Comment
Your program asks which pairs of doors are the closest.

Interactor
1
1 4

Comment
Pair {1, 4} is the closest.

Your program
? 0 5 1

Comment
Your program asks which pairs of doors are the closest.

Interactor
3
0 5
0 1
1 5

Comment
Pairs {0, 5}, {0, 1}, and {1, 5} are the closest.

Your program
! 4 5 3 0 2 1

Comment
Your program correctly outputs the order of the doors.

Please note that the sequences 0, 2, 1, 4, 5, 3 or 5, 4, 1, 2, 0, 3 (and a couple others) would also be correct answers in this case.

Scoring
Your score will be calculated as follows. Let k∗ be the actual number of queries asked by your program. Then, the number of points is given by the following formula:

ceil(100*min(1, (12000-k∗)/7800))

meaning that your score increases linearly from 0 to 100 as k∗ goes from 12000 to 4200.

Please note that if your program gives an incorrect answer, you will receive a score of 0 for that test case regardless of the number of queries asked.

The contraints for the problem are repeated once again below.
Problem Constraints
k = 12000, n = 500

Moreover, you can assume that each test case has been generated by first choosing n uniformly at random from all values of n satisfying the constraints of the problem, and then choosing the order of the doors uniformly at random from all orders of n doors satisfying the constraints of the problem.