Problem Description

This is an interactive problem.

There is a hidden partition that divides the integers $1, 2, \ldots, n$ into $\dfrac{n}{k}$ pairwise disjoint $k$-tuples. It is guaranteed that $n$ is a multiple of $k$. You need to find all hidden $k$-tuples by making queries.

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

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

$\lceil \cdot \rceil$ is the ceiling function. $\lceil x \rceil$ is the smallest integer not less than $x$. For example, $\lceil 7 \rceil = 7$, and $\lceil 3.14 \rceil = 4$.

Input Format

At the start, the interactor outputs one line with two integers $n$ and $k$ ($2 \le n \le 300$, $2 \le k \le n$, and $n$ is a multiple of $k$).

The hidden partition is kept by the interactor and will not be given directly.

After each time you output a valid query, the interactor returns one line with an integer $r$, which is the number of hidden $k$-tuples fully contained in your queried set.

Output Format

You can make queries in the following form:

$$\texttt{? c $x_1$ $x_2$ $\ldots$ $x_c$}$$

Here, $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 will return an integer $r$, which is the number of hidden $k$-tuples fully contained in $S$.

When you are sure about the answer, you need to output:

$$\texttt{! $a_1$ $a_2$ $\ldots$ $a_n$}$$

Here, $a_i$ denotes the tuple index of the tuple that contains element $i$. The indices must satisfy $1 \le a_i \le \dfrac{n}{k}$. If two elements belong to the same hidden tuple, their indices must be the same; if two elements belong to different hidden tuples, their indices must be different. The order of the tuple indices can be arbitrary.

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

Note that after each query or 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 query limit is exceeded, or the final answer is wrong, you will get Wrong Answer or Presentation Error.

The interactor is non-adaptive, meaning all $k$-tuples are fixed before the interaction starts and will not change as queries are made.

6 2

1

1

3

? 3 1 3 5

? 4 2 3 4 5

? 6 1 2 3 4 5 6

! 1 2 1 3 3 2

Hint

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

$$\def\arraystretch{1.5} \begin{array}{|l|c|} \hline \textbf{Program} & \textbf{Interactor} \\ \hline & \verb!6 2! \\ \hline \verb!? 3 1 3 5! & \verb!1! \\ \hline \verb!? 4 2 3 4 5! & \verb!1! \\ \hline \verb!? 6 1 2 3 4 5 6! & \verb!3! \\ \hline \verb|! 1 2 1 3 3 2| & \\ \hline \end{array}$$

• Query $\{1, 3, 5\}$: the tuple $\{1, 3\} \subseteq S$, so the answer is $1$.
• Query $\{2, 3, 4, 5\}$: the 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$.

Translated by ChatGPT 5