Kotlin Heroes: Episode 7 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 7:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

constructive algorithms

dfs and similar

graphs

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Biome Map

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp decided to generate a biome map for his game. A map is a matrix divided into cells $$$1 \times 1$$$. Each cell of the map must contain one of the available biomes.

Each biome is defined by two parameters: temperature (an integer from $$$1$$$ to $$$n$$$) and humidity (an integer from $$$1$$$ to $$$m$$$). But not for every temperature/humidity combination, a corresponding biome is available.

The biome map should be generated according to the following rules:

- each cell of the map belongs to exactly one biome;
- each available biome has at least one cell on the map;
- if two cells of the map are adjacent by the side and they belong to biomes with parameters ($$$t_1, h_1$$$) and ($$$t_2, h_2$$$), respectively, then the equality $$$|t_1-t_2| + |h_1-h_2| = 1$$$ holds;
- let the number of available biomes be equal to $$$k$$$, then the number of rows and columns of the map (separately) should not exceed $$$k$$$.

Help Polycarp generate a biome map that meets all the conditions described above (or report that this is impossible).

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10$$$) — maximum temperature and humidity parameters.

The following $$$n$$$ lines contain $$$m$$$ integers each $$$a_{i,1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 100$$$), where $$$a_{i, j}$$$ — the biome identifier with the parameters $$$(i, j)$$$, if $$$a_{i, j} \neq 0$$$, otherwise the biome with such parameters is not available.

All biome identifiers are different, and there are at least two biomes available.

Output

For each test case, print the answer in the following format:

- print $$$-1$$$ in a single line if there is no map that meets all the conditions;
- otherwise, in the first line, print two integers $$$h$$$ and $$$w$$$ — the number of rows and columns of the map, respectively. In the following $$$h$$$ lines, print $$$w$$$ integers — the identifiers of the biomes in the corresponding cells of the map.

Example

Input

4 2 3 0 2 5 0 1 0 3 5 0 3 4 9 11 1 5 0 10 12 0 6 7 0 0 2 2 2 0 0 5 1 2 13 37

Output

1 3 5 2 1 2 8 11 9 4 3 5 1 5 6 12 10 9 4 3 5 6 7 -1 1 2 13 37

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 07:49:28 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|