反复涂色 (color)

题目描述

Y 同学有一个 $H$ 行 $W$ 列的网格。令 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

每个格子被涂成白色或黑色。网格的初始状态由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 给出。如果 $S_i$ 的第 $j$ 个字符是 .，则格子 $(i, j)$ 是白色的；如果是 #，则格子 $(i, j)$ 是黑色的。

Y 同学将重复进行以下操作 $10^{100}$ 次：

同时对所有格子应用以下规则：

• 如果一个格子在操作前是白色的，当且仅当它周围至少存在一个黑色的相邻格子时，它在操作后变为黑色。这里的“相邻”定义为 $8$ 连通，即对于格子 $(x, y)$，格子 $(x', y')$ 与其相邻当且仅当它们满足 $\max(\vert x-x' \vert, \vert y-y' \vert) = 1$。
• 如果一个格子在操作前是黑色的，它在操作后变为白色。

请你帮 Y 同学求出 $10^{100}$ 次操作后每个格子的颜色。

输入格式

第一行包含两个正整数 $H$ 和 $W$。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串 $S_i$，表示网格的初始颜色状态。

输出格式

输出 $H$ 行，每行包含一个长度为 $W$ 的字符串，表示操作完成后的网格状态。

对于第 $i$ 行的第 $j$ 个字符，如果格子 $(i, j)$ 在 $10^{100}$ 次操作后是白色的，请输出 .，如果是黑色的，请输出 #。

样例

样例输入 #1

3 4
#.#.
.#..
#...

样例输出 #1

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

样例输入 #2

3 3
###
###
###

样例输出 #2

...
...
...

样例输入 #3

5 7
.#.....
.......
..#....
.......
....#..

样例输出 #3

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

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le H \times W \le 10^6$，$1 \le H, W \le 10^6$，且字符串 $S_i$ 仅由 . 和 # 组成。

特殊性质 A：保证初始状态下，网格中所有的字符均为 .。 特殊性质 B：保证 $H = 1$。