Poisoned Water Bottle Interactive Problem

This is an interactive IO problem. You are given n water bottles numbered from 1 to n, and exactly one of them contains poison. You have some lab mice, among which exactly one is mutated. The mutated mouse behaves oppositely to a normal mouse: if it drinks from the poisonous bottle it will survive, but if it drinks only safe water it will die within 59 seconds. Conversely, any normal mouse will die within 59 seconds if it drinks the poisoned water, and stay alive otherwise.

You have already spent 59 seconds testing, leaving you with only 1 second for your algorithm. Your goal is to determine the index of the poisoned bottle by issuing a series of queries following the interactive protocol described below:

1. You start by reading two integers n and maxk from standard input, where n is the total number of water bottles and maxk is the maximum number of mice you may use.
2. If you plan to use k mice, you must output k+1 lines. For each of the first k lines, the format is: 1 m B1 B2 ... Bm, which means you make one mouse drink from m bottles with indices B1, B2, ..., Bm. After these k lines, output an extra line containing just 2 to indicate that you require no further mice.
3. You will then receive k integers R₁, R₂, ..., R_k from standard input. For each i, R_i=0 indicates that the i-th mouse died (either a normal mouse that drank poison, or the mutated mouse that did not drink poison), and R_i=1 indicates that the mouse survived.
4. Finally, based on your queries and the responses, you must output a single integer—the index of the poisoned bottle.

Note: Due to the extreme time constraint (only 1 second of code execution time remains), you are allowed to design a strategy that possibly uses no queries at all. In the sample solutions below, a dummy solution is provided: no queries are issued (i.e. k = 0) and the answer is always set to 1.

inputFormat

The first line of input contains two space-separated integers: n (the number of water bottles) and maxk (the maximum number of mice you can use).

outputFormat

Your output must follow the interactive protocol. If you decide to use k mice, output k+1 lines: for each of the first k lines, provide a query of the form 1 m B1 B2 ... Bm, and then output a line with 2 to indicate no further queries. After reading k responses from standard input, output a single integer representing the index of the poisonous bottle.

Note: In the sample solutions below, a dummy strategy is implemented that uses no queries (i.e. k = 0). In that case, you simply output a single line with 2 followed by the final answer (here, always 1).

sample

1 0

2
1