#5705. 「COCI 2024/2025 #3」Bojanje

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #3 T3「Bojanje」

Marin 在竞技编程方面变得异常出色，他决定寻找一种新的爱好，以便在等待你赶上他的这段时间里打发时间。在你解决前面那些题目时，Marin 发现了他对绘画的热爱。

他拿出一张空白的白色画布，准备了两种颜色：红色和蓝色。他开始在画布上绘制完全水平和垂直的笔触，从一端一直延伸到相对的另一端。这张画布可以想象成一个 $n \cdot n$ 的网格，其中行和列的编号从 $1$ 到 $n$，且初始时完全是白色的。Marin 的每一次笔触可以想象为选择两种颜色中的一种，以及一行或一列，然后将该行/列中的所有单元格涂上所选颜色，而不管该区域之前是什么颜色。Marin 将进行有限次数的笔触来完成他的画作。

然而，他的朋友 Stjepan 发现了一幅画，看起来很像 Marin 的作品，但不确定它是否真的出自 Marin 之手。他发现的这幅画同样可以想象成一个 $n \times n$ 的网格，每个单元格或是白色、蓝色或红色。如果存在一种如上所述的在空白画布上的笔触序列，能够产生与所发现的画作完全一致的图像，那么这幅画就可能是 Marin 的作品。Stjepan 请求你帮助他确定这幅画是否可能是 Marin 的作品，如果是，则找出产生该画作的一组笔触序列。

输入格式

第一行包含一个正整数 $n$ $(1 \leq n \leq 2000)$。

接下来的 $n$ 行中，包含 $n$ 个整数 $a_{i, j}$ $(0 \leq a_{i, j} \leq 2)$，分别表示第 $i$ 行第 $j$ 列的颜色（$0$ 表示白色，$1$ 表示红色，$2$ 表示蓝色）。

输出格式

如果这幅画可能是 Marin 的作品，那么在第一行输出笔触的数量 $K$ $(0 \leq K \leq 4000)$。在接下来的 $K$ 行中，输出三个整数。第一个整数指示第 $i$ 次笔触是针对行还是列（$1$ 表示行，$2$ 表示列）。第二个数字指示执行笔触的行或列编号，第三个数字指示颜色，其表示方式与输入部分相同。

如果这幅画肯定不是 Marin 的作品，则在唯一的一行中输出 -1。

样例 1

输入

3
0 0 1
1 1 1
0 0 1

输出

2
2 3 1
1 2 1

样例 2

输入

3
1 1 2
2 1 1
2 1 1

输出

-1

样例 3

输入

4
0 1 2 1
2 2 2 1
0 1 2 1
1 1 2 1

输出

5
2 2 1
1 2 2
2 4 1
1 4 1
2 3 2

数据范围与提示

详细子任务附加限制及分值如下表所示。