Marin 在竞技编程方面变得异常熟练，他决定找一个新爱好，以便在等你赶上他的同时打发时间。在你解决之前的问题时，Marin 发现了他对绘画的热爱。

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

然而，他的朋友 Stjepan 发现了一幅类似于 Marin 作品的画，但不确定它是否真的是 Marin 画的。他发现的这幅画也可以想象成一个 $n \times n$ 的网格，其中每个单元格要么是白色、蓝色，要么是红色。如果存在一种在空白画布上进行上述笔触的序列，能够产生与所发现的图像完全相同的效果，那么这幅画就可能是 Marin 画的。Stjepan 请你帮他确定这幅画是否可能是 Marin 画的，如果是，请找到一个能产生该画作的笔触序列。

输入格式

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

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

输出格式

如果这幅画可能是 Marin 画的，则在第一行打印笔触次数 $K$ ($0 \le K \le 4000$)。

在接下来的 $K$ 行中，你应该打印三个整数。第一个整数表示第 $i$ 次笔触是在行上还是在列上（$1$ 表示行，$2$ 表示列）。第二个数字表示进行笔触的行或列的索引，第三个数字表示颜色，方式与输入部分描述的相同。

如果这幅画肯定不是 Marin 画的，则在第一行（也是唯一一行）打印 "-1"（不含引号）。

子任务

样例

样例输入 1

3
0 0 1
1 1 1
0 0 1

样例输出 1

2
2 3 1
1 2 1

样例输入 2

3
1 1 2
2 1 1
2 1 1

样例输出 2

-1

样例输入 3

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

样例输出 3

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