Replicate Replicate Rfplicbte

The owner of the Automatic Cellular Manufacturing corporation has patented a new process for the mass production of identical parts. The process uses a two dimensional lattice of cells, and every cell is either empty or filled. The details are proprietary.

At the start, some cells of the lattice are filled with a copy of the part to be reproduced. After that, the lattice repeats a discrete update step in which every cell changes state at the same time. The next state of a cell is decided by the nine cells made of itself and its eight neighbors. If an odd number of those nine cells are filled, the cell becomes filled in the next step, otherwise it becomes empty. Figure 1 shows several steps of the replication of a simple pattern made of three filled cells.

Figure 1. The replication process.

A bug has crept into the process. Right after each update step, one cell of the lattice might spontaneously flip its state. Figure 2 shows what might happen if one cell flipped after the first step and another cell flipped after the third step.

Figure 2. Errors in the replication process. This figure matches the first example input.

The original patterns are lost, and only the results of the replication remain. Those results may be corrupted. Find a smallest nonempty starting pattern that could have produced the given final pattern. The process ran for zero or more update steps, and after each step at most one cell flipped on its own.

The first line contains the width $w$ and the height $h$ of the bounding box of the final pattern ($1 \le w \le 300$, $1 \le h \le 300$).

Each of the next $h$ lines contains $w$ characters describing the final pattern. Each character is '.' for an empty cell or '#' for a filled cell. At least one cell is filled in the first row, in the last row, in the first column, and in the last column.

Print a smallest nonempty starting pattern that could have produced the given final pattern. The size of a pattern is the area of its bounding box. Use '.' for empty cells and '#' for filled cells, and use the minimum number of rows and columns needed to show the pattern. The smallest starting pattern that satisfies the rules is unique.