This is an interactive problem.
The Entomology department at Columbia wants to expand its colony of ants.
The colony currently consists of $$$n$$$ male and $$$n$$$ female ants, each numbered $$$1$$$ through $$$n$$$. The scientists want to find a female ant to mate with each male ant. Since ants are polyandrous, one female can mate with multiple males at once.
Two ants can mate only if they are attracted to each other. One male ant may be attracted to multiple female ants, and vice versa.
To find which pairs of ants are attracted to each other, the scientists can run experiments with the aid of an AI (Ant Inspection) tool by Ant-ropic. In one experiment, they take $$$x$$$ male ants and $$$y$$$ female ants, and place them in a cell. The AI observes their behaviour and reports one pair of ants which are attracted to each other, or that none exist. The cost of this experiment is $$$x + y$$$ dollars.
More formally, you can make the following queries to the interactor:
- "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" — run the experiment on male ants $$$i_1, i_2, \ldots, i_x$$$ and female ants $$$j_1, j_2, \ldots, j_y$$$. The interactor replies with some pair of attracted ants "$$$i_k \; j_\ell$$$", meaning that $$$i_k$$$-th male ant can mate with $$$j_\ell$$$-th female ant, or "$$$-1 \; -1$$$" if no such pair exists. The same pair may be reported in multiple experiments. The cost of this query is $$$x + y$$$ dollars.
After running some experiments, the scientists need to report, for each male ant, which female ant it can mate with, or $$$-1$$$ if no such ant exists. Since the scientists are on a budget, the total cost of all experiments may not exceed $$$35 \, 000$$$ dollars.
The only line of input contains an integer $$$n$$$ ($$$1 \leq n \leq 400$$$) — the size of the male and the female ant colonies.
After you read this line of input, the interaction begins with your first query.
To make a query, output a line (without quotes) in the following format:
- "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" ($$$1 \leq x, y \leq n$$$, $$$1 \leq i_1, i_2, \ldots i_x \leq n$$$, $$$1 \leq j_1, j_2, \ldots j_y \leq n$$$).
After each query, read two space-separated integers — the answer to the query. If an attracted pair exists, the answer will be "$$$i_k \; j_\ell$$$" for some $$$k$$$ and $$$\ell$$$ ($$$1 \leq k \leq x$$$, $$$1 \leq \ell \leq y$$$), indicating the attracted pair. Otherwise, the answer will be "$$$-1 \; -1$$$".
The cost of this query is $$$x + y$$$.
The total cost of all queries must not exceed $$$35 \, 000$$$.
An answer to the problem is a sequence $$$p_1, p_2, \ldots, p_n$$$, where $$$p_i$$$ is the index of a female ant with which the $$$i$$$-th male ant can mate, or $$$-1$$$ if no such ant exists.
Once you have determined an answer to the problem, print the line (without quotes) in the following format:
- "! $$$p_1 \; p_2 \ldots p_n$$$" ($$$p_i = -1$$$ or $$$1 \leq p_i \leq n$$$)
If there are multiple correct answers, output any.
After this, terminate the program.
The interactor in this task is not adaptive. In other words, the pairs of attracted ants do not change throughout the interaction.
If you make queries of total cost more than $$$35 \, 000$$$, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness Limit Exceeded verdict. To flush, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- see the documentation for other languages.
2 1 2 -1 -1
? 1 1 2 1 2 ? 1 2 2 1 2 ! 2 -1
In the sample test case, male ant $$$1$$$ is attracted to both female ants, and male ant $$$2$$$ is attracted to none. In the first query, the AI reveals one of the two attractions. In the second query, no attractions are found. The total cost of these queries is $$$6$$$.
| Название |
|---|