Reconstructing TensorFlow Logo from Projections

You are a die-hard fan of TensorFlow. In order to show your passion you want to reconstruct the TensorFlow logo in 3D from two projection images.

Consider a 3D space of size \(n \times m \times h\). You are given two projection matrices:

• A front projection: an \(n \times m\) matrix \(A\) with elements either 0 or 1.
• A right projection: an \(n \times h\) matrix \(B\) with elements either 0 or 1.

The projections are taken as follows:

• The front projection is obtained by shining light from the front. For each cell \((i,j)\) in \(A\), the cell is 1 if and only if there exists at least one small cube at some depth \(k\) (\(0 \le k < h\)) such that a cube is placed at \((i,j,k)\).
• The right projection is obtained by shining light from the left so that the shadow falls on the right side. For each cell \((i,k)\) in \(B\), the cell is 1 if and only if there exists at least one cube at some column \(j\) (\(0 \le j < m\)) such that a cube is placed at \((i,j,k)\).

You need to choose a collection of \(1 \times 1 \times 1\) cubes (which can be arbitrarily placed -- no gravity constraints) such that the resulting solid, when projected onto the front and right planes, gives exactly the two matrices provided. In the matrices, a 1 means that the projection cell is covered (shadow exists) and 0 means it is not.

If no valid configuration exists, output -1.

If a solution exists, you must find two solutions:

1. The solution using the minimum number of cubes.
2. The solution using the maximum number of cubes (by filling every allowed position).

If there are multiple solutions with the same number of cubes, output the lexicographically smallest one. For two solutions \(a\) and \(b\) (each considered as a sorted sequence of triples \((i,j,k)\) in ascending order where comparison is by \(i\), then \(j\), then \(k\)), solution \(a\) is lexicographically smaller than \(b\) if at the first index where they differ, the triple in \(a\) is smaller than the corresponding triple in \(b\). For example, [(0,0,0), (1,1,1)] is lexicographically smaller than [(1,1,1), (0,0,0)] when both lists are sorted.

Input/Output format details:

The input begins with three integers \(n\), \(m\) and \(h\). Then follow \(n\) lines describing the front projection matrix (each line contains \(m\) space‐separated integers 0 or 1), and then \(n\) lines describing the right projection matrix (each line contains \(h\) space‐separated integers 0 or 1).

If a solution exists, the output should be in the following format:

[min_count]
(i j k)  // one cube per line for the minimal solution, sorted in lex order
...
#
[max_count]
(i j k)  // one cube per line for the maximal solution, sorted in lex order
...

If no solution exists, output a single line with -1.

Note: Coordinates are zero-indexed. The cubes placed for each row (i.e. fixed i) are determined independently. For each row \(i\), let \(J\) be the set of columns \(j\) such that \(A[i][j]=1\) and \(K\) be the set of depths \(k\) such that \(B[i][k]=1\). A cube can only be placed at \((i,j,k)\) if \(j \in J\) and \(k \in K\).

For the minimal solution for a fixed row:

• If \(|J| \ge |K|\), you need to place exactly \(|J|\) cubes. You must assign to each \(j \in J\) a depth \(k\) (from \(K\)) such that the union of the chosen depths equals \(K\). To obtain the lexicographically smallest sequence (when sorted by \((i,j,k)\)), assign the value \(K[0]\) (the smallest element of \(K\)) to all positions by default and then, for the last few positions (i.e. those with largest \(j\)), replace the assignment with the remaining elements of \(K\) in increasing order.
• If \(|J| < |K|\), you need to place exactly \(|K|\) cubes. In this case, assign to each cube a column from \(J\) such that every column in \(J\) appears at least once. To get the lexicographically smallest assignment, by default assign \(J[0]\) (the smallest element of \(J)\) to all cubes and then, for the last few cubes (i.e. those corresponding to the largest depths), replace the assignment with the remaining elements of \(J\) in increasing order.

The maximal solution for a fixed row is simply all possible allowed positions, i.e. every pair \((j,k)\) with \(j \in J\) and \(k \in K\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(h\) (the dimensions of the 3D space).

The next \(n\) lines each contain \(m\) space‐separated integers (0 or 1), representing the front projection matrix.

The following \(n\) lines each contain \(h\) space‐separated integers (0 or 1), representing the right projection matrix.

outputFormat

If there is no solution, output a single line with -1.

If a solution exists, first output the minimal solution followed by a line containing only a single # character, and then output the maximal solution.

[min_count]
(i j k)  // one cube per line, sorted in lexicographical order
...
#
[max_count]
(i j k)  // one cube per line, sorted in lexicographical order
...

Coordinates are 0-indexed.

sample

1 1 1
1
1

1
0 0 0

1
0 0 0

</p>