Description

lien 们对于图像的处理与地球人一样，但是比较落后，所以容易出错。 一些概念：

两个黑像素直接连接当且仅当他们是相邻的（四联通） ；

两个黑像素间接连接当且仅当存在一条只由直接连接的黑像素构成的路径；

一个块是指一些黑像素，他们两两之间直接或者间接连接，且没有其余的黑像素可以被加入；

一个块是“和谐的”，当且仅当这个块中的任意两个间接相连的黑像素之间 的路径上黑像素个数=它们的曼哈顿距离。

现在 Alien 处理的图像有问题，可能有一些黑像素被处理成了白像素，使这个图变得不 和谐，而所有白像素不变。他们需要你重新处理这个图像，在改变最少黑像素个数的情况下 使得这个图和谐。

Format

Input

第一行两个整数 N，M，意义如上。 接下来 N 行，每行一个长度为 M 的字符串表示这一行的颜色， 其中”#”表示黑像素。

Output

输出共 N 行，每行一个长度为 M 的字符串，表示每一行的正确处理结果

Samples

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

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

Limitation

对于 100%数据 N，M≤50