Hide

Problem I
Inspecting Illumination

This is an interactive problem

The Zoldyck mansion is enormous, with dozens of rooms and hundreds of illuminating sources — light bulbs, chandeliers, lamps, etc.

You are recently hired by the Zoldyck family as a butler. Your daily job involves sitting in the illumination control room and control all the illuminating sources in the mansion.

In the control room, there are $n$ switches. Each switch controls exactly one illuminating source. Switches and illuminating sources are numbered from $1$ to $n$, inclusive. However, there is no documentation, so you do not know which switch controls which illuminating source.

Thus, your only choice is to repeat the following operation:

  • Toggle some of the switches (at least one).

  • Go around the entire mansion, check all the state of all $n$ illuminating sources.

As the mansion is enormous, you want to go around it at most $32$ times.

Interaction

First your program reads the integer $n$ $(1 \le n \le 1\, 000)$.

Then the following process repeats:

  • Your program writes to the standard output one of the following:

    • ASK $k \; a_1 \; a_2 \; \ldots \; a_ k$ ($1 \le k \le n, 1 \le a_ i \le n$ and all $a_ i$ are unique) — you toggle $k$ switches $a_1, a_2, \ldots , a_ k$, and want to know what are the $k$ illuminating sources which are toggled.

    • ANSWER $b_1 \; b_2 \; \ldots \; b_ n$ $(1 \le b_ i \le n)$ — you want to answer that the illuminating source $i$ is controlled by the switch $b_ i$.

  • If your program asks a query, $k$ integers will be available in the standard input, representing the illuminating sources which were toggled, in any order. Your program should then read them.

  • If your program prints an answer, it should then terminate. You are allowed to print an answer exactly once.

Note that you are allowed to interact at most $32 + 1 = 33$ times, $32$ interactions for asking queries and $1$ interaction for answering.

Note

After printing a query do not forget to output end of line and flush the output. Otherwise, your submission may be rejected. To do this, use:

  • fflush(stdout) or cout.flush() in C++;

  • System.out.flush() in Java;

  • stdout.flush() in Python.

Read Sample Interaction 1 Write
5
ASK 1 1
1
ASK 2 1 2
1 3
ASK 3 1 2 3
1 3 4
ASK 4 1 2 3 4
1 2 3 4
ASK 5 1 2 3 4 5
1 2 3 4 5
ANSWER 1 4 2 3 5

Please log in to submit a solution to this problem

Log in