Problem Description

This is an interactive problem.

There is an undirected unweighted graph with $n$ vertices.

This graph has a special property: there exists a one-to-one correspondence between a vertex $u \ (1 \leq u \leq n)$ and a pair of positive integers $(x, y) \ (1 \leq x \leq l, 1 \leq y \leq c)$, such that $n = l \cdot c$, and there is an edge between vertices $u, v$ if and only if the corresponding pairs $(x_u, y_u), (x_v, y_v)$ satisfy $|x_u - x_v| + |y_u - y_v| = 1$. In other words, this graph is isomorphic to an $l$-row $c$-column grid graph.

Now, you need to recover the structure of this graph using some queries. In each query, you need to provide a vertex $u \ (1 \leq u \leq n)$. The return value of the query is an array $\{d_i\}$ of length $n \ (1 \leq i \leq n)$, where $d_i$ is the number of edges on the shortest path between vertices $u$ and $i$.

You need to recover the structure of the graph using no more than $q$ queries.

Interaction Protocol

This problem contains multiple test cases.

First, an integer $T$ is given, denoting the number of test cases.

For each test case:

• First, an integer $n$ is given, denoting the number of vertices in the graph.
• Then, you may perform some queries. For each query, output an integer $u$, the vertex you query. Then, input $n$ integers $\{d_i\}$, the returned values of the query.
• When you are ready to give the answer, output an integer $0$, and then output your answer.

When outputting the answer:

• Output two integers $l, c$ on the first line.
• Next, output $l$ lines each containing $c$ integers, describing the correspondence you recovered. The number in row $i$, column $j$ is the index corresponding to $(i, j)$.

If there are multiple answers, you may output any one of them. An answer is considered correct if and only if it cannot be distinguished from the standard answer by any query. That is, in the grid graphs corresponding to these two answers, the number of edges on the shortest path between any pair of vertices is the same.

Please note: after each query or after outputting the answer, you should flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Java, use System.out.flush().
• In Python, use stdout.flush().
• In Pascal, use flush(output).
• For other languages, please refer to the corresponding documentation.

Input Format

See “Interaction Protocol”.

Output Format

See “Interaction Protocol”.

1
6

0 2 2 3 1 1

2 0 2 1 1 3

2 2 0 1 1 1

3 1 1 0 2 2

1 1 1 2 0 2

1 3 1 2 2 0

1

2

3

4

5

6

0
2 3
2 5 1
4 3 6

2
1



2

1 0

0
1 1
1

2

0
2 1
1
2

Hint

Explanation of Sample $1$

For the sample, the following $3$-row $2$-column grid graph is also a correct output.

3 2
4 2
3 5
6 1

The left side is the grid graph corresponding to the sample, and the right side is the grid graph corresponding to the output above.

Scoring Rules

For a subtask, let $q_{\max}$ be the maximum number of queries you used among all testdata in this subtask.

If the interaction protocol is invalid, your program exceeds the time limit, or your answer is incorrect, or $q_{\max} > q$, then your score is $0$.

Otherwise, for subtasks $1 \sim 3$, you get full score. For subtask $4$, your score is given by the table below:

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1 \leq T \leq 10^3$, $1 \leq n \leq 10^5$, and $\sum n \leq 3 \times 10^5$.

In some testdata, the interactor is adaptive. That is, the structure of the graph may change according to your queries. However, it is guaranteed that after each query, there exists at least one answer consistent with all returned values so far.

Translated by ChatGPT 5