Description

自动化蜂窝制造公司的所有者刚刚为一种生产相同零件的新工艺申请了专利。她的方法使用了一个二维的两态单元格网格，每个单元格要么是“空的”，要么是“填充的”。具体细节当然是专有的。

最初，网格中的一组单元格被填充为要复制的零件的副本。在一系列离散步骤中，网格中的每个单元格通过检查自身状态及其八个周围邻居的状态来同时更新其状态。如果这九个单元格中有奇数个是填充的，则该单元格在下一个时间步的状态将是填充的，否则将是空的。图 G.1 显示了一个由三个填充单元格组成的简单图案的复制过程中的几个步骤。

图 G.1：复制过程。

然而，过程出现了一个错误。在每次更新步骤之后，网格中的一个单元格可能会自发地翻转其状态。例如，图 G.2 显示了如果一个单元格在第一次时间步后翻转其状态，另一个在第三次时间步后翻转其状态可能会发生的情况。

图 G.2：复制过程中的错误。此图对应于样例输入 $1$。

不幸的是，原始图案丢失了，只剩下（可能被破坏的）复制结果。你能编写一个程序来确定可能导致给定最终图案的最小可能非空初始图案吗？

Input Format

输入的第一行包含两个整数 $w (1 \le w \le 300)$ 和 $h (1 \le h \le 300)$，其中 $w$ 和 $h$ 是最终图案的边界框的宽度和高度。接下来的 $h$ 行，每行包含 $w$ 个字符，给出了最终图案。每个字符要么是 ‘.’（表示空单元格），要么是 ‘#’（表示填充单元格）。在第一行、最后一行、第一列和最后一列中至少有一个填充单元格。

Output Format

显示一个可能导致给定图案的最小尺寸非空图案，假设在复制过程的每个阶段最多有一个单元格自发改变状态。图案的大小是其边界框的面积。如果有多个可能的最小尺寸非空起始图案，任何一个都将被接受。使用字符 ‘.’ 表示空单元格，‘#’ 表示填充单元格。使用显示图案所需的最少行和列。

10 10
.#...#...#
##..##..##
##.#.##...
##.#.##...
.#...#####
...##..#.#
......###.
##.#.##...
#..#..#..#
##..##..##

.#
##

8 8
##..#.##
#.####.#
.#.#.#..
.##.#.##
.#.#.#..
.##.#.##
#..#.###
##.#.##.

####
#..#
#.##
###.

5 4
#....
..###
..###
..###

#

Hint

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。