Problem Description

As a die-hard fan of TensorFlow, you want to reconstruct the TensorFlow icon from two projection images.

Assume you have a 3D space of dimensions $n \times m \times h$, and two projection matrices (one $n \times m$ matrix and one $n \times h$ matrix, with elements being either $0$ or $1$). You need to calculate a set of $1 \times 1 \times 1$ small cubes such that when these cubes are placed in the 3D space, the orthographic projections (front projection with light behind the solid and right projection with light from the left side) match the given projection images. If there is no solution, output $-1$. If there is a solution, you need to calculate two sets that meet the conditions, one with the minimum number of small cubes and one with the maximum. Assume that the placement of cubes is not affected by gravity (i.e., cubes can be placed freely in the 3D space, even suspended without support). A $1$ in the matrix represents a shaded area, and a $0$ represents an unshaded area.

If there are multiple solutions, you need to output the solution with the smallest lexicographical order. A solution $a$ is lexicographically smaller than solution $b$ if and only if for the first pair of different numbers in the two solutions, the number in $a$ is smaller than the number in $b$.

For example, the solution $[(0, 0, 0), (1, 1, 1)]$ is lexicographically smaller than the solution $[(1, 1, 1), (0, 0, 0)]$.

Input Format

The first line contains three integers $n, m, h \ (1 \leq n, m, h \leq 100)$, representing the dimensions of the 3D space.

The next $n$ lines, each containing $m$ characters $0$ or $1$, describe the front projection. A $1$ represents a shaded area, and a $0$ represents an unshaded area.

The following $n$ lines, each containing $h$ characters in the same format, describe the right projection.

Output Format

If there is no solution, output $-1$ on the first line.

If there is a solution, the first line should output an integer $k_{max}$, representing the maximum number of small cubes in a solution that meets the requirements.

The next $k_{max}$ lines should each output three integers $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$, representing the positions of the $k_{max}$ small cubes in the lexicographically smallest solution with the maximum number of cubes.

The next line should output an integer $k_{min}$, representing the minimum number of small cubes in a solution that meets the requirements.

The next $k_{min}$ lines should each output three integers $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$, representing the positions of the $k_{min}$ small cubes in the lexicographically smallest solution with the minimum number of cubes.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

2 2 2
00
00
11
11

Sample Output #2

-1

Sample Input #3

2 3 2
101
011
10
11

Sample Output #3

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

Notes

A cube placed at $(x, y, z)$ will create a shaded area at position $(x, y)$ in the front projection and at position $(x, z)$ in the right projection.

Coordinates are numbered starting from $0$.

见题面 Input 部分

见题面 Output 部分