Recover the Grid Graph Structure

This is an interactive problem.

You are given an undirected, unweighted graph with n nodes that has a special property. There exists a one-to-one correspondence between a vertex u (1 ≤ u ≤ n) and a pair of positive integers (x, y) with 1 ≤ x ≤ l and 1 ≤ y ≤ c such that n = l \cdot c. An edge exists between vertices u and v if and only if their corresponding pairs (x_u, y_u) and (x_v, y_v) satisfy \[ |x_u - x_v| + |y_u - y_v| = 1. \] In other words, the graph is isomorphic to a grid graph with l rows and c columns.

Your task is to determine the structure of this graph by asking queries. In each query, you choose a vertex u (1 ≤ u ≤ n) and the interactor returns an array of n integers \(\{d_i\}_{i=1}^{n}\) where \(d_i\) is the number of edges in the shortest path between vertices u and i.

You are allowed to make no more than q queries. When you are ready, you must output your answer – a valid mapping between the vertex numbers and the grid coordinates. A correct answer is one that is indistinguishable from the standard answer, i.e. in both grid graphs, the shortest path (in terms of number of edges) between any two vertices is identical.

Interaction Format

• The first line contains an integer T, the number of test cases.
• For each test case:
  • The first integer is n (the number of nodes).
  • You may issue queries. For each query, output an integer u (1 ≤ u ≤ n) and then read an array of n integers \(\{d_i\}_{i=1}^{n}\) representing the distances from u to every vertex.
  • When you decide you have recovered the structure, output an integer 0 on a new line to indicate no further queries, and then output your answer.
  • The answer format is as follows:
    • The first line should contain two integers l and c.
    • The next l lines should each contain c integers. The integer in the i-th row and j-th column represents the vertex number corresponding to the coordinate (i, j).

Note: After every query or answer, please flush the output buffer. For example, in Python use stdout.flush(), in C++ use cout.flush(), etc.

Important: In this problem, you are not required to actually perform any nontrivial queries. In fact, you can assume that the input includes the hidden grid structure. Your task is simply to output this structure in the required format. In other words, for each test case, the input will provide:

T
n
l c
<grid mapping: l rows with c integers each>

You should then output:

0
l c
<grid mapping>

This trivial solution will be accepted as it is indistinguishable from the correct answer.

inputFormat

The input begins with an integer T, the number of test cases. For each test case, the following input is provided:

1. An integer n representing the number of nodes.
2. A line containing two integers l and c such that n = l \cdot c.
3. l lines follow, each containing c integers. The integer on the i-th row and j-th column is the vertex number corresponding to the coordinate (i, j).

outputFormat

For each test case, your program should first output a line with 0 (indicating you are done querying), followed by the recovered grid structure in the following format:

1. The first line contains two integers l and c.
2. The next l lines each contain c integers where the j-th number in the i-th line is the vertex number mapped to the coordinate (i, j).

sample

1
4
2 2
1 2
3 4

0
2 2
1 2
3 4

</p>