Wires Puzzle

This is an interactive problem. Your program interacts with the judges' program through standard input and standard output.

Friends are planning a puzzle with the following structure. There are $n$ similar wires put through an opaque pipe. One end of the pipe is the left end and the other is the right end. At each end, the friends see $n$ wires labeled by distinct integers from 1 to $n$, but a wire can have different labels at the two ends.

The goal of the puzzle is to match the wire ends. For each $i$ from 1 to $n$, find the number $a_i$ such that the wire labeled $i$ on the right end is labeled $a_i$ on the left end.

You can make the following queries. Choose an integer $k$ ($1 \le k \le n$) and divide the wires at the right end into $k$ non-empty groups, connecting all wires inside the same group. A special device then reports, for each pair of wires at the left end, whether their right ends are connected. This tells you which left labels correspond to wires from the same group.

You must find the correspondence using exactly three such queries.

To understand the interaction, study the example in the hint below.

Consider the example above.

There are 4 wires.

The first query has three groups. Wires with right labels 1 and 2 are connected, and wires with right labels 3 and 4 are each in a group by themselves.

The judges' program responds that wires with left labels 2 and 3 are in the same group, and wires with left labels 1 and 4 are each in a group by themselves.

From this response, the program knows that left labels 2 and 3 correspond to right labels 1 and 4 in some order, and left labels 1 and 4 correspond to right labels 3 and 4 in some order.

The second query has two groups. Wires with right labels 1, 2, and 3 are connected, and the wire with right label 4 is in a group by itself.

The judges' program responds that wires with left labels 2, 3, and 4 have their right ends connected.

The program concludes that the wire with right label 4 has left label 1, so the wire with right label 3 has left label 4.

The third query separates the wires with right labels 1 and 2. After this, the correspondence is fully determined.