Hidden $$$k$$$-Tuples
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden partition of the integers $$$1, 2, \ldots, n$$$ into $$$\frac{n}{k}$$$ disjoint $$$k$$$-tuples. It is guaranteed that $$$k \mid n$$$.

You need to determine all hidden $$$k$$$-tuples through queries.

In each query, you may choose a set $$$S \subseteq \{1, 2, \ldots, n\}$$$, and the interactor will return an integer indicating how many hidden $$$k$$$-tuples are entirely contained in $$$S$$$.

The number of queries must not exceed $$$n\lceil \log_2 n \rceil$$$.

Input

At the start of your program, the interactor outputs a line with two integers $$$n$$$ and $$$k$$$.

Here $$$2 \le n \le 300$$$, $$$2 \le k \le n$$$, and $$$k \mid n$$$.

The hidden partition is stored by the interactor and is not given directly.

After each valid query you output, the interactor returns a line with a single integer $$$r$$$ — the number of hidden $$$k$$$-tuples entirely contained in the set you queried.

Output

You may make queries of the following form:

? c $$$x_1$$$ $$$x_2$$$ $$$\ldots$$$ $$$x_c$$$

where $$$0 \le c \le n$$$, and $$$x_1, x_2, \ldots, x_c$$$ must be pairwise distinct integers satisfying $$$1 \le x_i \le n$$$.

This query means you choose the set $$$S=\{x_1,x_2,\ldots,x_c\}$$$. The interactor returns an integer $$$r$$$ — the number of hidden $$$k$$$-tuples entirely contained in $$$S$$$.

When you have determined the answer, output:

! $$$a_1$$$ $$$a_2$$$ $$$\ldots$$$ $$$a_n$$$

where $$$a_i$$$ denotes the tuple number that element $$$i$$$ belongs to. The numbering must satisfy $$$1 \le a_i \le \frac{n}{k}$$$. Two elements in the same hidden tuple must have the same number; two elements in different hidden tuples must have different numbers. The ordering of tuple numbers is arbitrary.

The number of queries must not exceed $$$n\lceil \log_2 n \rceil$$$. After outputting the final answer, your program should terminate immediately.

Note that after each query or the final answer, you must flush the output buffer. For example, in C++ you can use:

fflush(stdout);

or

cout « flush;

If your output format is invalid, the number of queries exceeds the limit, or the final answer is wrong, you will receive Wrong Answer or Presentation Error.

The interactor is non-adaptive, meaning all $$$k$$$-tuples are fixed before the interaction begins and do not change based on your queries.

Example
Input
6 2

1

1

3
Output
? 3 1 3 5

? 4 2 3 4 5

? 6 1 2 3 4 5 6

! 1 2 1 3 3 2
Note

In the example below, $$$n = 6$$$, $$$k = 2$$$, and the hidden tuples are $$$\{1, 3\}$$$, $$$\{2, 6\}$$$, $$$\{4, 5\}$$$.

ProgramInteractor
6 2
? 3 1 3 51
? 4 2 3 4 50
? 6 1 2 3 4 5 63
! 1 2 1 3 3 2

Query $$$\{1,3,5\}$$$: tuple $$$\{1,3\} \subseteq S$$$, so the answer is $$$1$$$.

Query $$$\{2,3,4,5\}$$$: tuple $$$\{4,5\} \subseteq S$$$, so the answer is $$$1$$$.

Query $$$\{1,2,3,4,5,6\}$$$: all three tuples are contained, so the answer is $$$3$$$.

Output ! 1 2 1 3 3 2 means: elements $$$1, 3$$$ form group $$$1$$$; elements $$$2, 6$$$ form group $$$2$$$; elements $$$4, 5$$$ form group $$$3$$$.