투영

당신이 TensorFlow 팬이라는 사실은 모두가 알고 있다. 그래서 두 개의 투영으로 TensorFlow 로고를 다시 만들어 보라는 도전을 받았다.

$n \times m \times h$ 크기의 3차원 공간과 두 개의 투영(크기가 $n \times m$이고 $n \times h$인 두 행렬, 원소는 0 또는 1)이 주어진다. 왼쪽과 앞쪽에서 빛이 들어올 때, 3차원 공간 안에 놓인 정육면체들이 만들어 내는 그림자가 주어진 투영 행렬과 일치하도록 정육면체를 배치하는 방법을 구해야 한다. 불가능하면 −1을 출력한다. 가능하면 정육면체 개수가 최대인 배치와 최소인 배치를 각각 하나씩 구해야 한다. 중력은 없다고 가정한다. 즉 정육면체는 받침 없이 놓인 위치에 그대로 있다. 1은 그림자, 0은 빛을 나타낸다.

가능한 답이 여러 개라면 사전순으로 가장 작은 것을 출력한다. 답 A가 답 B보다 사전순으로 작다는 것은, 두 답에서 처음으로 달라지는 수가 A에서 더 작다는 뜻이다.

예를 들어 답 [(0, 0, 0),(1, 1, 1)]은 [(1, 1, 1),(0, 0, 0)]보다 작다.

첫째 줄에 공백 하나로 구분된 세 정수 $n, m, h$ ($1 \le n, m, h \le 100$)가 주어진다. 이는 공간의 크기이다.

다음 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 각 문자는 1 또는 0이다. 1은 그림자 영역, 0은 빛 영역을 나타내며, 앞쪽에서 비추는 빛에 대한 투영을 나타낸다.

그다음 $n$개의 줄에는 각각 $h$개의 문자가 같은 형식으로 주어지며, 왼쪽에서 비추는 빛에 대한 투영을 나타낸다.

첫째 줄에는 답이 없으면 −1을, 있으면 주어진 두 투영을 만들어 내면서 공간에 놓을 수 있는 정육면체 개수의 최댓값 $k_{max}$를 출력한다.

다음 $k_{max}$개의 줄에는 정육면체 개수가 최대인 답 중 사전순으로 가장 작은 답에 포함되는 정육면체의 좌표 $x, y, z$ ($0 \le x < n$, $0 \le y < m$, $0 \le z < h$)를 한 줄에 하나씩 출력한다.

그다음, 답이 존재하는 경우에만, 주어진 두 투영을 만들어 내면서 공간에 놓을 수 있는 정육면체 개수의 최솟값 $k_{min}$을 한 줄에 출력한다.

이어서 다음 $k_{min}$개의 줄에는 정육면체 개수가 최소인 답 중 사전순으로 가장 작은 답에 포함되는 정육면체의 좌표 $x, y, z$ ($0 \le x < n$, $0 \le y < m$, $0 \le z < h$)를 한 줄에 하나씩 출력한다.

좌표 $(x, y, z)$에 놓인 정육면체는 $n \times m$ 투영의 $x$번째 줄 $y$번째 열과, $n \times h$ 투영의 $x$번째 줄 $z$번째 열에 그림자를 만든다(0부터 인덱스를 센다).