Description

You are a hardcore fan of TensorFlow, so you want to reconstruct the TensorFlow logo from two projection images.

Suppose you have a 3D space of size $n \times m \times h$, and two projection images (an $n \times m$ matrix and an $n \times h$ matrix, with each entry being $0$ or $1$). You need to find a set of $1 \times 1 \times 1$ unit cubes such that, after placing these cubes into the 3D space, the front orthographic projection (the projection formed on the back side of the solid when light shines on the front face) and the right projection (the projection formed on the right side of the solid when light shines on the left face) are consistent with the given projection images. If there is no solution, output $-1$. If there is a solution, you need to compute two valid sets: one with the minimum number of unit cubes, and one with the maximum number. Assume gravity does not matter (i.e., unit cubes can be placed anywhere in the 3D space; they can float without support). In the matrices, $1$ means the position is covered by shadow, and $0$ means it is not covered by shadow.

If there are multiple solutions, you need to output the lexicographically smallest one. A solution $a$ is lexicographically smaller than a solution $b$ if and only if, at the first position where they differ, the number in $a$ is smaller than the corresponding number in $b$.

For example, the solution $[(0, 0, 0), (1, 1, 1)]$ is lexicographically smaller than $[(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 size of the 3D space.

In the next $n$ lines, each line contains $m$ characters $0$ or $1$. Here, $1$ means covered by shadow, and $0$ means not covered. These $n \times m$ characters describe the front projection.

In the next $n$ lines, each line contains $h$ characters in the same format. These $n \times h$ characters describe the right projection.

Output Format

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

If there is a solution, output an integer $k_{max}$ on the first line, representing the maximum number of unit cubes among all valid solutions.

In the next $k_{max}$ lines, output three integers $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$ per line, representing the positions of the $k_{max}$ unit cubes in the lexicographically smallest solution among those with the maximum number of cubes.

Then output an integer $k_{min}$ on the next line, representing the minimum number of unit cubes among all valid solutions.

In the next $k_{min}$ lines, output three integers $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$ per line, representing the positions of the $k_{min}$ unit cubes in the lexicographically smallest solution among those with the minimum number of cubes.

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

Hint

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

Coordinates are numbered starting from $0$.

Translated by ChatGPT 5