CF525D.Arthur and Walls

Finally it is a day when Arthur has enough money for buying an apartment. He found a great option close to the center of the city with a nice price.

Plan of the apartment found by Arthur looks like a rectangle n × m consisting of squares of size 1 × 1. Each of those squares contains either a wall (such square is denoted by a symbol "*" on the plan) or a free space (such square is denoted on the plan by a symbol ".").

Room in an apartment is a maximal connected area consisting of free squares. Squares are considered adjacent if they share a common side.

The old Arthur dream is to live in an apartment where all rooms are rectangles. He asks you to calculate minimum number of walls you need to remove in order to achieve this goal. After removing a wall from a square it becomes a free square. While removing the walls it is possible that some rooms unite into a single one.

终于到了亚瑟攒够钱买房的日子。他找到了一处绝佳的房源，位于市中心附近，价格也很合理。

亚瑟找到的这套公寓的平面图是一个 $n \times m$ 的矩形，由若干 $1 \times 1$ 的小方格组成。每个小方格要么是一堵墙（在平面图中用符号 * 表示），要么是空地（在平面图中用符号 . 表示）。

公寓中的一个“房间”是指由空地构成的最大连通区域；两个方格若共享一条公共边，则视为相邻。

亚瑟一直以来的梦想，是住进一套所有房间都是矩形的公寓。他请你计算：为实现这一目标，最少需要拆除多少堵墙？拆除一堵墙后，该方格即变为空地。在拆墙过程中，一些原本分离的房间可能合并为一个房间。

The first line of the input contains two integers n, m (1 ≤ n, m ≤ 2000) denoting the size of the Arthur apartments.

Following n lines each contain m symbols — the plan of the apartment.

If the cell is denoted by a symbol "*" then it contains a wall.

If the cell is denoted by a symbol "." then it this cell is free from walls and also this cell is contained in some of the rooms.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$），表示阿瑟公寓的尺寸。

接下来的 $n$ 行，每行包含 $m$ 个字符，表示公寓的平面图。

若某个格子用符号 * 表示，则该格子为一堵墙。

若某个格子用符号 . 表示，则该格子无墙，并且属于某一个房间。

Output n rows each consisting of m symbols that show how the Arthur apartment plan should look like after deleting the minimum number of walls in order to make each room (maximum connected area free from walls) be a rectangle.

If there are several possible answers, output any of them.

输出 n 行，每行包含 m 个字符，表示在删除最少数量的墙壁后，Arthur 的公寓平面图应呈现的样式，使得每个房间（即不含墙壁的最大连通区域）均为矩形。

若存在多种可能的答案，输出任意一种即可。