Antonia's Ants

This is an interactive problem.
Antonia is studying the behavior of ants from a nearby colony. For her experiment, she will place $N$ candies in a straight line on the ground, numbered from $1$ to $N$ in order. She can choose the color of each candy.

From previous observations, Antonia knows that each ant leaves the colony and starts at any one of the candies. It then walks along the line, repeatedly moving from its current candy to the candy immediately to its left or right. Before returning to the colony, the ant visits every candy at least once. It may visit a candy more than once and may continue walking after it has visited every candy.

To study the routes the ants take, Antonia uses a system that records only the colors of the candies they visit, in order. She needs your help to reconstruct the sequences of visited candies from these records.

Your task is to develop a program that first chooses the colors of the candies and then reconstructs the sequences of visited candies from the recorded color sequences. For this to be possible, the coloring that you choose must ensure that no two different sequences of visited candies produce the same color sequence. We call such a coloring valid.

A valid coloring can always be obtained by using $N$ different colors, one for each candy. However, Antonia wants to use candies with as few different colors as possible.

Interaction

First, read a line with an integer $N$ ($2 \le N \le 10^{5}$) indicating the number of candies.

Then output a line with an integer $K$ followed by $N$ integers ${C_1}, {C_2}, \ldots, {C_N}$ ($1 \le C_i \le K$), where $K$ is the number of different colors used and $C_i$ is the color of candy $i$. You must provide a valid coloring that uses the minimum number of different colors. If several such colorings exist, you may output any of them.

After that, read a line with an integer $Q$ ($1 \le Q \le 100$) indicating the number of recorded color sequences. Each sequence corresponds to a different ant, and all sequences use the coloring you provided. Then, repeat the following $Q$ times, once per color sequence:

• Read a line with an integer $M$ ($M \ge N$) followed by $M$ integers ${S_1}, {S_2}, \ldots, {S_M}$ ($1 \le S_i \le K$), where $M$ is the length of the sequence of visited candies, and $S_i$ is the color of the $i$-th candy in this sequence.

• Output a line with $M$ integers ${P_1}, {P_2}, \ldots, {P_M}$ ($1 \le P_i \le N$), where $P_i$ is the number of the $i$-th candy in the sequence of visited candies.

The sum of $M$ over all recorded color sequences does not exceed $4 \times 10^{5}$.

Each color sequence is guaranteed to correspond to an ant that visits every candy at least once, moving only between neighboring candies.

The judge program is adaptive, which means that $Q$ and the recorded color sequences may depend on your outputs.

Your solution will be rejected if the coloring is not valid, $K$ is not minimum, or any reconstruction is wrong. In that case the interaction may end at any time, not necessarily immediately after the incorrect output.

Example

Indented lines are the interactor’s; the others are your program’s.

Example 1

          2
2 1 2
          2
          2 1 2
1 2
          5 2 1 2 1 2
2 1 2 1 2

In this case there are $N=2$ candies.

The number of different colors ($K=2$) is minimum: with a single color, the sequences of visited candies $1\ 2$ and $2\ 1$ would produce the same color sequence. In the sample, candy $1$ has color $1$ and candy $2$ has color $2$.

Then there are $Q=2$ recorded color sequences, each corresponding to a different ant. Taking into account the chosen colors, the color sequence $1\ 2$ can only come from the sequence of visited candies $1\ 2$, and the color sequence $2\ 1\ 2\ 1\ 2$ can only come from the sequence of visited candies $2\ 1\ 2\ 1\ 2$.

Example 2

            4
4 1 2 3 4
            1
            6 2 3 4 3 2 1
2 3 4 3 2 1

Notice that this interaction would be rejected, because it uses more colors than necessary. It is included only to illustrate the interaction format.

In this case $N=4$, $K=4$, $Q=1$ and $M=6$. The color sequence $2\ 3\ 4\ 3\ 2\ 1$ can only come from the sequence of visited candies $2\ 3\ 4\ 3\ 2\ 1$. The coloring is valid and the reconstruction is correct. However, a valid coloring with fewer than four colors exists for $N=4$, so $K$ is not minimum.