上学的路上,凯伦迷上了手机上的益智游戏!
游戏玩法如下。在每个级别中,您都有一个包含 n 行和 m 列的网格。每个单元格最初包含数字 0。
一次移动包括选择一行或一列,并将该行或该列中的所有单元格加 1。
要赢得关卡,在完成所有移动后,第 i 行第 j 列的单元格中的数字应等于 gi, j。
凯伦被困在一个关卡上,她想知道一种使用最少步数来通关这一关卡的方法。请帮助她完成这项任务!
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100),分别表示网格中的行数和列数。
接下来的 n 行每行包含 m 个整数。特别是,第 i 行中的第 j 个整数包含 gi, j (0 ≤ gi, j ≤ 500)。
输出
如果出现错误且实际上无法突破关卡,则输出单个整数 -1。
否则,在第一行输出一个整数 k,即通关所需的最小移动次数。
接下来的 k 行应每行包含以下内容之一,按照必须完成的顺序描述移动:
- 第 x 行,(1 ≤ x ≤ n) 描述“选择第 x 行”形式的移动。
- col x, (1 ≤ x ≤ m) 描述“选择第 x 列”形式的移动。
如果有多个最优解,则输出其中任意一个。
示例
输入 #1
3 5 2 2 2 3 2 0 0 0 1 0 1 1 1 2 1
输出 #1
4 row 1 row 1 col 4 row 3
输入 #2
3 3 0 0 0 0 1 0 0 0 0
输出 #2
-1
输入 #3
3 3 1 1 1 1 1 1 1 1 1
输出 #3
3 row 1 row 2 row 3
注意
在第一个测试用例中,Karen 有一个 3 行 5 列的网格。她可以执行以下 4 个动作来通关:
在第二个测试用例中,Karen 有一个 3 行 3 列的网格。很明显,不可能超越关卡;执行任何移动都会在网格上创建三个 1,但要求中心只能有一个 1。
在第三个测试用例中,Karen 有一个 3 行 3 列的网格。她可以执行以下 3 个动作来通关:
请注意,这不是唯一的解决方案;另一个解决方案是第 1 列、第 2 列、第 3 列。