Polycarp 决定为他的游戏生成一张生物群落地图。地图是一个分为单元格 $$$1 \times 1$$$ 的矩阵。地图的每个单元格必须包含一个可用的生物群落。
每个生物群系由两个参数定义:温度(从 $$$1$$$ 到 $$$n$$$ 的整数)和湿度(从 $$$1$$$ 到 $$$m$$$ 的整数)。但并非对于每种温度/湿度组合,都有相应的生物群系可用。
生物群系地图应根据以下规则生成:
- 地图的每个单元格都属于一个生物群系;
- 每个可用的生物群落在地图上至少有一个单元格;
- 如果地图的两个单元格相邻并且它们分别属于参数为 ($$$t_1, h_1$$$) 和 ($$$t_2, h_2$$$) 的生物群落,则等式 $$$|t_1-t_2| + |h_1-h_2| = 1$$$ 成立;
- 让可用生物群落的数量等于$$$k$$$,那么地图的行数和列数(单独)不应超过$$$k$$$。
帮助 Polycarp 生成满足上述所有条件的生物群落地图(或报告这是不可能的)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 20$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10$$$) – 最大温度和湿度参数。
以下 $$$n$$$ 行包含 $$$m$$$ 个整数 $$$a_{i,1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 100$$$),其中 $$$a_{i, j}$$$ — 带有参数的生物群落标识符$$$(i, j)$$$,如果$$$a_{i, j} \neq 0$$$,否则具有此类参数的生物群落不可用。
所有生物群落标识符都不同,并且至少有两个可用的生物群落。
输出
对于每个测试用例,按以下格式打印答案:
- 如果没有满足所有条件的地图,则在一行中打印$$$-1$$$;
- 否则,在第一行中,打印两个整数 $$$h$$$ 和 $$$w$$$ - 分别是地图的行数和列数。在接下来的 $$$h$$$ 行中,打印 $$$w$$$ 整数 - 地图相应单元格中生物群落的标识符。
示例
输入 #1
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
输出 #1
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