B. Permute-inator
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

Asadullo had an array $$$p[0], p[1], \ldots, p[n - 1]$$$, where each number from $$$0$$$ to $$$n-1$$$ occurs exactly once in some order.

However, evil Dr. Dilyor has stolen Asadullo's array. Sadly, Asadullo doesn't remember any information about his array. Dr. Dilyor proposed a game where Asadullo can give some queries and Dr. Dilyor will answer them.

Let's say Asadullo chooses some sequence of integers $$$x[0], x[1], \ldots, x[m-1]$$$ of size $$$m$$$ ($$$0 \le x[i] \le n-1$$$). Then, Dr. Dilyor returns the number of indices $$$0 \le i \le m - 2$$$ such that $$$p[x[i]] \gt p[x[i + 1]]$$$. Note that the values of the sequence $$$x$$$ do not have to be distinct. Also, the size $$$m$$$ can be chosen independently for each query.

Dr. Dilyor can answer only $$$10\;000$$$ such queries, and the total size of sequences should not exceed $$$10^6$$$. Help Asadullo to restore his array.

Interaction

First, you should read an integer $$$n$$$ – the size of the array. ($$$1 \le n \le 128$$$)

To make a query, use the following format:

? m x[0] x[1] ... x[m-1]

Then, you will receive an integer $$$k$$$ – the number of indices $$$0 \le i \le m - 2$$$ such that $$$p[x[i]] \gt p[x[i + 1]]$$$.

Once you found the array, print it in the following format:

! p[0] p[1] ... p[n-1]

After this, you must immediately terminate the program.

After printing a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout), cout.flush(), or cout«endl in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
see documentation for other languages.

If you make more than $$$10\;000$$$ queries, or the sum of values $$$m$$$ exceeds $$$10^6$$$, or you incorrectly guess the array $$$p$$$, you will get verdict Wrong Answer.

Scoring
GroupAdd. constraintsPoints
$$$0$$$examples$$$0$$$
$$$1$$$$$$n \le 7$$$$$$5$$$
$$$2$$$—$$$95$$$

Also, you can get partial score in the 2nd subtask. Let $$$q$$$ be the maximum number of queries among all tests in subtask 2. Then, your score will be as follows:

ConditionPoints
$$$10\;000 \lt q$$$$$$0$$$
$$$1000 \lt q \le 10\;000$$$$$$8$$$
$$$700 \lt q \le 1000$$$$$$19$$$
$$$127 \lt q \le 700$$$$$$15 + 70 \cdot \frac{128}{q}$$$
$$$q \le 127$$$$$$95$$$
Example
Input
6

2

1
Output

? 5 0 2 5 0 3

? 3 1 2 1

! 3 0 2 5 1 4
Note

Here $$$p$$$ is $$$[3, 0, 2, 5, 1, 4]$$$.

First, Asadullo made a query with $$$x = [0, 2, 5, 0, 3]$$$. As $$$p[x[0]] = 3 \gt 2= p[x[1]]$$$ and $$$p[x[2]] = 4 \gt 3 = p[x[3]]$$$, Dr. Dilyor returned $$$2$$$.

Then, Asadullo made another query with $$$x = [1, 2, 1]$$$. Dr. Dilyor returned $$$1$$$, because $$$p[x[1]] = 2 \gt 0 = p[x[2]]$$$.

And using intuition, Asadullo found out that $$$p=[3, 0, 2, 5, 1, 4]$$$.