eolymp
bolt
Try our new interface for solving problems
Problems

Projection

Projection

Time limit 1 second
Memory limit 128 MiB
prb11280.gif

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged to recreate the TensorFlow logo from two projections.

Consider that you have a 3D volume, n * m * h, and two projections (two matrices with dimensions n * m and n * h with elements 0 and 1). You are asked to compute a possible sets of cubes that must be placed inside the 3D volume such that the 3D object created with the cubes throws the shadows specified by the projection-matrices, when the light comes from left and front. If it is not possible, just print -1. If it is possible you must find exactly two sets, one with the maximum amount of cubes and one with the minimum amount. You can assume there is no gravitation (the cubes are located inside the 3D volume exactly where they are placed, without requiring any support). We assume that 1 represents shadow and 0 represents light.

If there are multiple such solutions, you must output the minimum lexicographic one. One solution a is lexicographically smaller than another solution b if the first number that differs between the two solutions is smaller in a than in b.

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

Input data

The first line contains three integers separated by a single space n, m, h (1n, m, h100) - the volume dimensions.

Each of the next n lines contains m characters, each being either 1 or 0 representing either a shadow area (1) or a light area (0), describing the projection from the light in the front.

Each of the next n lines contains h characters, with the same format as above, describing the projection from the light on the left.

Output data

The output should contain on the first line one number, either -1 if there is no solution or k[max] representing the maximum number of cubes we can assign in the volume that will generate the two projections given in the input.

The next k[max] lines should contain triplets of numbers x, y, z (0x < n, 0y < m, 0z < h) representing the cubes chosen in the lexicographically smallest solution with maximum number of cubes. Then, only if there is a solution, one more line follows containing k[min], the minimum number of cubes we can assign in the volume that will generate the two projections given in the input.

After that, the next k[min] lines should contain triplets of numbers x, y, z (0x < n, 0y < m, 0z < h) representing the cubes in the lexicographically smallest solution with minimum number of cubes.

Examples

Input example #1
5 3 3
111
010
010
010
010
111
100
110
100
100
Output example #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

Note

A cube at coordinates (x, y, z) will generate a shadow at line x and column y in the n * m projection and line x and column z in the n * h projection (indexed from 0).

Source 2019 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, October 19, Problem G