题目描述

你是一个 TensorFlow 的死忠粉，因此，你想要从两个投影图形来还原出 TensorFlow 的图标。

假定你有一个 3D 空间，尺寸为 $n \times m \times h$，以及两个投影图形（一个 $n \times m$ 的矩阵和一个 $n \times h$ 的矩阵，矩阵里的元素都为 $0$ 或 $1$）。你需要计算出一些 $1 \times 1 \times 1$ 的小正方体的集合，使得这些正方体放入 3D 空间后构成的立体的正投影（光照立体正面在立体后侧形成的投影）和右投影（光照立体左面在立体右侧形成的投影）与题目给定的投影图形一致。如果无解，输出 $-1$。如果有解，你需要计算出两个满足条件的集合，一个包含的小正方体数量最少，另一个最多。假定正方体的摆放不受重力影响（即小正方体在 3D 空间中可以随意放置，悬空也不需要支撑）。规定矩阵中的 $1$ 代表有阴影遮住，$0$ 代表无阴影遮住。

如果有多解，你需要输出字典序最小的解。一个解 $a$ 字典序比解 $b$ 小，当且仅当对于两个解中第一对不相同的数字，$a$ 中的数字小于 $b$ 中的。

例如，解 $[(0, 0, 0), (1, 1, 1)]$ 比解 $[(1, 1, 1), (0, 0, 0)]$ 字典序更小。

输入格式

第一行包含三个整数 $n, m, h \ (1 \leq n,m,h \leq 100)$，代表 3D 空间的尺寸。

接下来的 $n$ 行中，每一行包含 $m$ 个字符 $0$ 或 $1$，其中 $1$ 代表有阴影遮住，$0$ 代表无阴影遮住。这 $n \times m$ 个字符描述了一个正投影。

接下来的 $n$ 行中，每一行包含 $h$ 个字符，格式同上。这 $n \times h$ 个字符描述了一个右投影。

输出格式

如果无解，仅在第一行输出 $-1$ 即可。

如果有解，第一行输出一个整数 $k_{max}$，代表满足题目要求的解中小正方体个数的最大值。

接下来 $k_{max}$ 行中每行输出三个整数 $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$，代表小正方体最多的解中字典序最小的解的 $k_{max}$ 个小正方体的放置位置。

接下来一行输出一个整数 $k_{min}$，代表满足题目要求的解中小正方体个数的最小值。

接下来 $k_{min}$ 行中每行输出三个整数 $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$，代表小正方体最少的解中字典序最小的解的 $k_{min}$ 个小正方体的放置位置。

5 3 3
111
010
010
010
010
111
100
110
100
100

14
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 1 0
2 1 0
2 1 1
3 1 0
4 1 0
8
0 0 0
0 1 1
0 2 2
1 1 0
2 1 0
2 1 1
3 1 0
4 1 0

2 2 2
00
00
11
11

-1

2 3 2
101
011
10
11

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

提示

一个放置在 $(x, y, z)$ 的小正方体会在正投影的 $(x, y)$ 位置产生一个有阴影遮住的区域，并在右投影的 $(x, z)$ 位置产生一个有阴影遮住的区域。

坐标从 $0$ 开始编号。