407869: GYM102911 E Experiment!

This is an interactive problem.

The PIPAC (Philippine Institute of Pure and Applied Chemistry) is an independent scientific institute which lies between Faura Hall and the School of Management in the Ateneo de Manila University. Despite residing in Ateneo, it is an independent entity from the university, so students are generally not permitted to enter the facilities. PIPAC occasionally hosts guided tours of their labs for those curious of what secrets lie behind its enigmatic white walls.

Alice is on one such tour, and when the organizers heard that she was a programmer, they decided to entertain her with a hands-on puzzle.

Alice is presented with $$$1000$$$ containers of unknown compounds, labeled $$$1, 2, 3, \dots, 1000$$$. Each container holds exactly one type of compound, and no compound appears in more than one different container.

She can choose any subset of the containers, take a sample from each, and dissolve all the samples together into one mixture. Then, she can take this mixture to the lab, where a high-tech computer then prints out a list of all the compounds identified in the mixture, in no particular order.

Alice's task is to identify the compound in each of the $$$1000$$$ containers. Using the high-tech computer is expensive and time-consuming, so Alice is challenged to use it as few times as possible. In particular, she is assured that her task is possible in 10 uses or less. She seems to be having some trouble—could you help her out?

The judge first outputs a single line containing a single integer $$$T$$$, the number of test cases; there will always be exactly $$$T=5$$$ test cases in this problem. Each test case then proceeds as follows.

The judge outputs a line containing a single integer $$$N$$$, the number of unknown compounds; there will always be exactly $$$N=1000$$$ compounds in this problem.

The judge begins by secretly generating $$$N$$$ distinct strings, the names of the $$$N$$$ compounds. Each name consists of no more than 3 upper or lowercase English letters, and no two different compounds share the same name. The names of the compounds are case-sensitive.

You have two types of queries available to you.

If you wish to use the machine, output a single line containing the word MIX. Then, indicate which containers you would like to test. First, output a positive integer $$$n$$$, from $$$1$$$ to $$$N$$$ inclusive, indicating the number of different containers you will be sampling from. Then, output $$$n$$$ distinct whitespace-separated integers, meaning a sample is to be taken from each of the containers with these labels.

The judge will then respond with a single line containing $$$n$$$ space-separated strings, the compounds identified in the mixture you sent in no particular order.

If you are ready to give your final answer, output a single line containing the word ANSWER. Then, output $$$N$$$ whitespace-separated strings, the names of the compounds in the containers from $$$1$$$ to $$$1000$$$ (in that order).

The judge will then respond with a single line containing a $$$0$$$ if you were incorrect, or a $$$1$$$ if you were correct. If your program receives a $$$0$$$, then no further input (for the rest of the test cases) will be given from the judge. In such a case, you should terminate immediately to prevent an Idleness Limit Exceeded verdict. If your program receives a $$$1$$$, then simply proceed with the next test case.

There will be exactly $$$T=5$$$ test cases.

If you identified any of the compounds incorrectly, you get $$$0$$$ points. Otherwise, let $$$Q$$$ be the maximum number of times you used the MIX query in any of the test cases. Then, scoring is as follows.

Subtask 1 (15 points): $$$Q \leq 1000$$$

Subtask 2 (15 points): $$$Q \leq 999$$$

Subtask 3 (15 points): $$$Q \leq 750$$$

Subtask 4 (10 points): $$$Q \leq 667$$$

Subtask 5 (10 points): $$$Q \leq 500$$$

Subtask 6 (10 points): $$$Q \leq 250$$$

Subtask 7 (9 points): $$$Q \leq 100$$$

Subtask 8 (8 points): $$$Q \leq 11$$$

Subtask 9 (8 points): $$$Q \leq 10$$$

For illustration, Alice is allowed a practice round with just one test case and only $$$4$$$ unknown compounds. Let's examine her sample interaction.

Contestant          Judge
                    1
                    4
MIX
3
1 2 4
                    KBr ZnO NaH
MIX
2
3 4
                    ZnO CuS
MIX
1
1
                    KBr
ANSWER
KBr NaH CuS ZnO
                    1

Alice decides to MIX together $$$3$$$ different compounds by taking samples from containers $$$1$$$, $$$2$$$, and $$$4$$$.

The judge then responds that Alice's mixture contains KBr, ZnO, and NaH.

Alice then decides to MIX together $$$2$$$ different compounds by taking samples from containers $$$3$$$ and $$$4$$$.

The judge then responds that Alice's mixture contains ZnO and CuS.

Finally, Alice decides to MIX together just $$$1$$$ compound by taking a sample from container $$$1$$$.

The judge then responds that Alice's mixture contains KBr.

Alice is now confident in her logic and ready to ANSWER. She reports that,

• Container $$$1$$$ contains KBr.
• Container $$$2$$$ contains NaH.
• Container $$$3$$$ contains CuS.
• Container $$$4$$$ contains ZnO.

The judge then responds with a $$$1$$$ to tell Alice that she is correct!