Cellular Replication Restoration

The Automatic Cellular Manufacturing corporation has developed a process to replicate a given two‐dimensional part using a cellular automaton. The automaton operates on a rectangular grid where every cell is either empty (0) or filled (1). Initially, a copy of the part (a finite pattern of filled cells) is placed on the grid (all other cells are empty). In each discrete time step the grid is updated synchronously: each cell updates its state to filled if an odd number of cells in its 3×3 block (itself and its 8 neighbours) are filled; otherwise it becomes empty. In addition, after every update step, a bug may occur causing at most one cell in the entire grid to flip its state (from 0 to 1 or vice‐versa).

Unfortunately, the original part (the initial pattern) has been lost. Instead, you are given the resulting pattern after t replication steps (each step consisting of a deterministic update followed by an optional error flip). Your task is to find a smallest possible nonempty initial pattern (measured by the total number of filled cells) that could have produced the given final pattern under some sequence of error flips. If there are several possible answers, output any one. In the output, you must print the initial pattern in its minimal bounding box (i.e. remove any all‐empty rows or columns from the borders).

Note on the update rule: For a cell at position \((i,j)\) with state \(s_{i,j}\), let its 3×3 neighbourhood be \(\{s_{i+\delta,j+\epsilon}:\;\delta,\epsilon\in\{-1,0,1\}\}\) (cells outside the grid are assumed to be empty, i.e. 0). Then the state in the next step is given by:

[ s'{i,j} = \begin{cases}1,& \text{if } \sum{\delta=-1}^1\sum_{\epsilon=-1}^1 s_{i+\delta,j+\epsilon} \equiv 1 ; (\bmod;2),\0,& \text{otherwise.}\end{cases} ]

After this deterministic update, you may optionally select at most one cell anywhere in the grid and flip its state. This constitutes one replication step. The final pattern is obtained after t such steps.

inputFormat

The first line contains three integers n, m and t (1 ≤ n, m ≤ 4, 1 ≤ t ≤ 3), where n and m are the number of rows and columns of the final pattern. Each of the next n lines contains a string of m characters, each of which is either '0' (empty) or '1' (filled), representing the final pattern after t replication steps.

Note: The grid is small so that a brute‐force search over initial patterns is possible. Cells outside the given grid are assumed to be empty.

outputFormat

First, output two integers r and c representing the number of rows and columns of the minimal bounding box of your candidate initial pattern. Then output r lines, each containing c characters (each either '0' or '1'), representing the initial pattern. The initial pattern must be nonempty and must be such that there exists some sequence of error flips (at most one per replication step) that transforms it into the given final pattern after t steps.

If there are multiple answers then any one is accepted.

sample

1 1 1
1

1 1
1