1s 512MB

题目描述

沙皇热衷于观赏乒兵球，乒兵球规则是这样的：地上有一个 $n$ 行 $m$ 列的白球矩形，两个神金兵分别进行操作，一个选中一些球染红，一个选中一些球染蓝，总所周知，红+蓝=紫，所以如果一个球同时被染上了红色和蓝色，那么这个球就会变成紫色

现在沙皇会给定一个颜色要求，染色要做到有且仅有他指定的地方是紫色，其他位置的球可以是红蓝白中任意一种，不过这也太简单了！所以沙皇还要求染上这个红色的球要能够四联通，染上蓝色的当然也要四联通

不过由于沙皇宫殿的地毯与紫色不太相配，所以沙皇不想让边界染上紫色，也就是不会在第 $1$ 行、第 $n$ 行、第 $1$ 列，第 $m$ 列指定染紫色

别的神金兵都是两两联手共同解题，你作为神金兵大统领当然是一个人就可以给出红色和蓝色的染色方案了！

输入格式

第一行两个数 $n$，表示白球矩形有 $n$ 行 $m$ 列。

然后接着 $n$ 行 $m$ 列输入一个没有空格间隔的 $\texttt{.#}$ 矩阵 $M$， $M_{i,j}=\texttt{`#'}$ 表示沙皇指定第 $i$ 行第 $j$ 列的白球要被染成紫色，$M_{i,j}=\texttt{`.'}$ 则代表这里不能为紫色。

输出格式

首先输出一个 $n$ 行 $m$ 列的 $\texttt{.#}$ 矩阵，$\texttt{`#'}$ 表示这个位置染红，$\texttt{`.'}$ 表示仍然是白色。

然后中间间隔一行，再输出一个 $n$ 行 $m$ 列的 $\texttt{.#}$ 矩阵，$\texttt{`#'}$ 表示这个位置染蓝，$\texttt{`.'}$ 表示仍然是白色。

样例一输入

5 5
.....
.#.#.
.....
.#.#.
.....

样例一输出

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

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

样例二输入

7 13
.............
.###.###.###.
.#.#.#.#.#.#.
.###.###.###.
.#.#.#.#.#.#.
.###.###.###.
.............

样例二输出

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

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

数据范围与约束

对于 $100 \%$ 的数据， $3 \le n,m \le 500$

$\text{subtask1 (5pts)}$ ： $n=m=3$

$\text{subtask2 (20pts)}$ ： $n,m \le 5$

$\text{subtask3 (25pts)}$ ： $n,m \le 10$

$\text{subtask4 (25pts)}$ ： $n,m \le 50$

$\text{subtask5 (25pts)}$ ： $n,m \le 500$

从 $\text{subtask2}$ 开始，每个子任务依赖前一个子任务