Cartogram
This is a problem about constructing cartograms.
Here's what a cartogram looks like:
Briefly, a cartogram is a map in which some thematic mapping variable – such as travel time, population, or GNP – is substituted for land area or distance. Observe how in the above cartogram, places with more population are represented with larger area. The problem will be formalized as follows.
In this problem, we wish to visualize how many people in each country WRONGLY believe that the Earth is shaped like an oblate spheroid.
For the purposes of this problem, we index the countries on Earth by integers .
A map of the planet Earth is represented by an RECTANGULAR grid.
Each cell in the rectangular grid is represented by a non-negative integer whose value is at most . A cell represented by a means that it is water, and is not owned by any country. A cell represented by a positive integer means that it is owned by country . This means that each cell can be owned by at most one country.
Two cells in the grid are adjacent if they share an edge. Since the planet Earth is definitely not a sphere, the leftmost cells of the map are NOT adjacent to the rightmost cells of the map. Same goes for the topmost and bottommost cells.
A set of cells is said to be contiguous if for any two cells , there exists a sequence of cells on Earth such that
- for each non-negative integer .
- is adjacent to for each positive integer .
A map is said to be valid if and only if it satisfies the following two properties:
Map represents each country as a map of contiguous set of cells.
Each country owns at least one cell in map .
Given a map , two countries are neighbors in the map if they own cells which are adjacent to each other.
Two valid maps and are said to be similar if and only if it preserves the property of "being neighbors". More precisely, two maps and are similar if and only if the following condition is true:
For any pair of different countries and , and are neighbors in the map if and only if they are neighbors in the map .
Our research shows that country has exactly million misinformed people who think that Earth is spherical.
You are given a valid map of the planet Earth. The cells owned by each country in map represent its geographical territory.
Your task is to find a valid map such that:
Map is similar to Map .
In map , cells owned by countries represent the amount of misinformed people in each country. That is, for any two countries and , if country owns cells in Map and country owns cells in Map , then .
Map has at most cells.
Input Format
The first line of input contains , the number of test cases.
The first line of test case contains three space-separated integers , and .
The second line contains space-separated integers .
The next lines describe the grid. In particular, the th line contains space-separated integers representing a row of map .
Constraints
Subtask 1 (3 points):
Subtask 2 (6 points):
Subtask 3 (10 points):
Subtask 4 (14 points):
Subtask 5 (38 points):
Subtask 6 (18 points):
Subtask 7 (11 points):
No additional constraints.
Output Format
For each test case, first output a line containing two space-separated integers and denoting that are the dimensions of the new map, map .
The following lines must describe the map in the same format as the input map , that is, the th following line must contain space-separated integers denoting the th row of map .
If there are multiple solutions, you may output any. It is guaranteed that at least one solution exists.
Sample Input 0
1
3 5 4
6 8 6 4
1 1 1 2 4
3 3 2 2 2
3 0 2 2 0
Sample Output 0
4 3
1 2 4
1 2 4
1 2 2
3 3 3
Explanation 0
Here is an illustration of the sample input and output:
Although the output map doesn't look anything like the input map , you can show that they are similar. Furthermore, you can verify that the number of cells in each country in map represents its number of misinformed individuals. Hence, this output is valid.
xxxxxxxxxxusing namespace std;int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;}