Grid Game
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: constructive algorithms, games, graph matchings, greedy, interactive

This is an interactive problem.

You are given a grid with $$$n$$$ rows and $$$m$$$ columns. You need to fill each cell with a unique integer from $$$1$$$ to $$$n \cdot m$$$.

After filling the grid, you will play a game on this grid against the interactor. Players take turns selecting one of the previously unselected cells from the grid, with the interactor going first.

On the first turn, the interactor can choose any cell from the grid. After that, any chosen cell must be orthogonally adjacent to at least one previously selected cell. Two cells are considered orthogonally adjacent if they share an edge. The game continues until all cells have been selected.

Your goal is to let the sum of numbers in the cells selected by you be strictly less than the sum of numbers in the cells selected by the interactor.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$4 \le n, m \le 10$$$) — the number of rows and columns in the grid.

Interaction format:
First, output $$$n$$$ lines, each containing $$$m$$$ integers, representing the integers that you filled in the grid. Each integer from $$$1$$$ to $$$n \cdot m$$$ should appear exactly once.

Then, the game begins. The interactor and you take turns outputting coordinates to select a cell for $$$n \times m$$$ turns, with the interactor starting first.

On each player's (either you or the interactor) turn, the player will output two integers $$$i$$$ and $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$), denoting that the player has selected the cell on the $$$i$$$-th row and $$$j$$$-th column. This cell should not have been selected in a previous round. Additionally, if it is not the first turn, the cell must be orthogonally adjacent to at least one previously selected cell.

If any of your outputs are invalid, the jury will output "-1" and you will receive a Wrong Answer verdict.

At the end of all $$$n \cdot m$$$ turns, if the sum of numbers in the cells selected by you is not strictly less than the sum of numbers in the cells selected by the interactor, the jury will output "-1" and you will receive a Wrong Answer verdict.

If your program has received a Wrong Answer verdict, it must terminate immediately. Otherwise, you may receive an arbitrary verdict because your solution might be reading from a closed stream.

After outputting, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

In this problem, hacks are disabled.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Note that this is an example game and does not necessarily represent the optimal strategy for both players.

First, we fill a $$$4 \times 4$$$ grid with unique integers from $$$1$$$ to $$$16$$$ in the following way:

$$$2$$$$$$3$$$$$$4$$$$$$10$$$$$$12$$$$$$6$$$$$$11$$$$$$15$$$$$$5$$$$$$13$$$$$$16$$$$$$8$$$$$$9$$$$$$7$$$$$$1$$$$$$14$$$

Next, the game begins.

1. The interactor first selects $$$(3, 4)$$$, which is the number $$$8$$$. For this selection, the interactor could choose any number. From the next selection onwards, each chosen number has to be adjacent to any previously selected number.
2. We select $$$(2, 4)$$$, which is the number $$$15$$$, adjacent to $$$(3, 4)$$$.
3. The interactor selects $$$(4, 4)$$$, which is the number $$$14$$$, adjacent to $$$(3, 4)$$$.
4. We select $$$(4, 3)$$$, which is the number $$$1$$$, adjacent to $$$(4, 4)$$$.
5. $$$\ldots$$$
6. This is continued until all numbers are selected.

In the end, the numbers we selected were $$$[15, 1, 16, 5, 4, 2, 11, 13]$$$, and the numbers selected by the interactor were $$$[8, 14, 7, 9, 10, 3, 6, 12]$$$. The sum of the numbers we selected is $$$67$$$, which is less than the sum of the numbers selected by the interactor $$$69$$$. Therefore, we have won this game.

Example input:
1
4 4




3 4

4 4

4 2

4 1

1 4

1 2

2 2

2 1

Example output:
2 3 4 10
12 6 11 15
5 13 16 8
9 7 1 14

2 4

4 3

3 3

3 1

1 3

1 1

2 3

3 2

Editorial:
Hint 1
Notice that if the problem requires our selected numbers' sum to be greater than the interactor's sum, instead of smaller, the essence of the problem changes.
Hint 2
Depending on whether $$$n \cdot m$$$ is odd or even, we can use different methods to fill the grid and adapt our game strategy.
Hint 3
When $$$n \cdot m$$$ is odd, we can adopt a strategy that forces the interactor to choose the largest number, $$$n \cdot m$$$.
Hint 4
When $$$n \cdot m$$$ is even, we can divide the grid into several tiles. After the interactor chooses a number from a tile, we immediately choose from the same tile.
Hint 5
We set each tile size to be even, ensuring we always select the second number from each tile.
Hint 6
When $$$n \cdot m$$$ is even, we can create some T-shaped tiles at the edges of the grid, where each T-shaped tile consists of a cell on the edge and three cells surrounding it.
Hint 7
Place a small number in the center of each T-shaped tile, and fill the surrounding three cells with large numbers. This way, we can always select the smallest number from each T-shaped tile, except for the interactor's first choice.
Hint 8
When $$$n \cdot m$$$ is even, we only need to create $$$4$$$ T-shaped tiles and divide the remaining cells into several dominos, each containing two adjacent numbers. This method of filling numbers is sufficient to ensure that the sum of the numbers we choose is smaller.
Solution
Notice that if the problem requires our selected numbers' sum to be greater than the interactor's sum, instead of smaller, the essence of the problem changes. Specifically, when $$$n \cdot m$$$ is odd, the interactor will select one more number than us. If the goal is to have a greater sum of numbers, the interactor will have an advantage; conversely, if the goal is to have a smaller sum, we will have an advantage.
Depending on whether $$$n \cdot m$$$ is odd or even, we can use different methods to fill the grid and adapt our game strategy. Here, we will explain these two methods and strategies in detail.
When $$$n \cdot m$$$ is odd, we can adopt a strategy that forces the interactor to choose the largest number, $$$n \cdot m$$$. Specifically, we can divide the grid into:
• $$$\lfloor \frac{n \cdot m}{2} \rfloor$$$ dominos ($$$1 \times 2$$$ or $$$2 \times 1$$$ tiles), each containing two adjacent numbers.
• In the remaining single cell, we place the largest number.
Our strategy is as follows: If the interactor chooses a number from a domino and the other number has not yet been chosen, we choose that number; otherwise, we choose any valid number from the dominos. This ensures that:
• In each domino, both we and the interactor select one number. Proof: The interactor cannot choose both numbers in a domino because as soon as they choose the first one, we immediately choose the second one. Therefore, we select at least one number in each domino. We cannot select two numbers in any domino because our total number of selections would exceed the number of dominos, which equals our total number of selections. Hence, we exactly select one number in each domino.
• The interactor will inevitably choose the largest number. Proof: Since we only choose numbers from the dominos, the remaining largest number will not be selected by us.
In the worst case, we will choose the larger number in each domino. However, the interactor will always select the largest number. Therefore, in this scenario, our sum will be less than the interactor's sum by $$$n \cdot m - \lfloor \frac{n \cdot m}{2} \rfloor = \lceil \frac{n \cdot m}{2} \rceil$$$.
When $$$n \cdot m$$$ is even, we can divide the grid into several tiles. After the interactor chooses a number from a tile, we immediately choose from the same tile. We set each tile size to be even, ensuring we always select the second number from each tile.
If a small number is surrounded by large numbers in a tile, as the second chooser we can choose the small number. We place the small numbers on the edges of the grid, where the number of surrounding cells is odd, ensuring that each tile has an even number of cells. This tiling arrangement gives us a significant advantage; only a few such tiles are needed, while the rest of the grid can be filled with dominos containing adjacent numbers, making our sum of numbers smaller. Here are the detailed descriptions of grid filling and game strategy:
We divide the grid into:
• $$$4$$$ T-shaped tiles, each with a small number at the edge of the grid, surrounded by three large numbers.
• $$$\frac{n \cdot m - 16}{2}$$$ dominos, each containing two adjacent numbers.
Specifically, we define $$$[1, 4]$$$ as small numbers, and $$$[n \cdot m - 11, n \cdot m]$$$ as large numbers. Numbers $$$[n \cdot m - 11, n \cdot m - 9]$$$ surround number $$$1$$$, $$$[n \cdot m - 8, n \cdot m - 6]$$$ surround number $$$2$$$, $$$[n \cdot m - 5, n \cdot m - 3]$$$ surround number $$$3$$$, and $$$[n \cdot m - 2, n \cdot m]$$$ surround number $$$4$$$.
Assuming $$$n \le m$$$, we divide the grid as follows:
• For $$$n = 4$$$ and $$$m = 4$$$, as well as $$$n = 4$$$ and $$$m = 5$$$, we manually divide the grid.    This is a specific layout for a $$$4 \times 4$$$ grid, with bold lines indicating tiles division, green cells representing small numbers, and red cells representing large numbers.      This is a specific layout for a $$$4 \times 5$$$ grid, with additional settings, where yellow cells represent adjacent numbers in dominos.
• For $$$m \geq 6$$$, we place two T-shaped tiles and two dominos in the top left and top right $$$4 \times 3$$$ areas. The remaining part of the top four rows can be filled with vertical dominos. For rows beyond the top four, if $$$m$$$ is even, we fill them with horizontal dominos; if $$$m$$$ is odd, we fill them with vertical dominos.    This is a specific layout for a $$$5 \times 8$$$ grid, an example where $$$m$$$ is even.      This is a specific layout for a $$$6 \times 7$$$ grid, an example where $$$m$$$ is odd.
Our strategy is as follows: After the interactor chooses a number from a tile, we will immediately choose the smallest valid number from the same tile. This ensures that the interactor can only start choosing from the large numbers in each T-shaped tile, allowing us to choose the small number, except for the small number that the interactor initially chooses.
Next, we will analyze why this strategy ensures a smaller sum. For each T-shaped tile, if the interactor did not initially choose from this tile, we can at least choose the smallest and largest numbers; if the interactor initially chose from this tile, we can at least choose the second smallest and largest numbers. We find that if the interactor chooses to start from the T-shaped tile, they take away our smallest number and give us the second smallest number. Thus, in the worst case, the interactor starts choosing from number $$$4$$$, where the difference between the smallest and second smallest numbers in that tile is the largest. In dominos, we assume we will choose the larger number.
In the worst case, the calculation of our sum of numbers minus the interactor's sum of numbers is: $$$(1 - (n \cdot m - 11) - (n \cdot m - 10) + (n \cdot m - 9)) + \\ (2 - (n \cdot m - 8) - (n \cdot m - 7) + (n \cdot m - 6)) + \\ (3 - (n \cdot m - 5) - (n \cdot m - 4) + (n \cdot m - 3)) + \\ (-4 + (n \cdot m - 2) - (n \cdot m - 1) + n \cdot m) + \\ (n \cdot m - 16) / 2 = \\ 20 - 1.5 \cdot n \cdot m$$$
When $$$n$$$ and $$$m$$$ are at their minimum, this value is the largest and unfavorable for us. However, when $$$n$$$ and $$$m$$$ are at their minimum of $$$4$$$, our sum of numbers is still $$$4$$$ less than the interactor's ($$$20 - 1.5 \cdot 4 \cdot 4 = -4$$$).