405066: GYM101773 F Toroidal Picture

Amir likes to draw rectangles in toroidal grids. Whenever he gets a white rectangular grid consisting of h rows and w columns, he starts drawing several (maybe zero) rectangles with sides parallel to the grid lines each consisting of several grid cells. He may draw a new rectangle only if it does not intersect or touch with any of the previous rectangles. After choosing a suitable rectangle, he paints all of its cells black.

Formally, he performs the following steps. Suppose he got an h × w rectangular grid. The grid is toroidal meaning that the left side of the rectangle is identified with the right side of the rectangle, and the bottom side is identified with the top side of the rectangle. Introduce a coordinate system with lower left cell having coordinates (0, 0) and the top right cell having coordinates (w - 1, h - 1). Amir chooses four integers x₁, x₂, y₁, y₂ (x₁ ≤ x₂, y₁ ≤ y₂) and considers a set R of all cells with coordinates where x₁ ≤ x ≤ x₂ and y₁ ≤ y ≤ y₂ as candidates to be painted black. He may proceed with painting all of the cells in set R if no cell from set R is already black and if there is no cell that shares a common side or a corner with some of the already existing black cells.

Colleagues of Amir are not much into his drawings, but they are fond of solving problems. Amir decided to exploit this fact to attract their attention to his beautiful drawings. He chose one of his pictures drawn on a rectangular grid of height h and width w and performed an operation of circular shift with each of the grid rows. A circular shift of a row by k (0 ≤ k ≤ w - 1) positions to the left consists of moving first k cells after the remaining w - k cells (without changing the relative order of a cells in each of the parts). In particular, a circular shift by 0 positions does not change a row at all. Amir could have shifted each row by its own number of positions.

Amir presented the modified drawing to his colleagues and now they are curious what was the original picture. Can you help them by restoring any of the possible initial pictures?

The first line of input contains two positive integers h, w (1 ≤ h·w ≤ 500 000).

The following h lines describe the modified picture. Each line consists of w characters and represents a row of a picture, character . stands for a white cell and character X stands for a black cell.

Print a rectangular grid such that it can be obtained from the input one by applying a circular shift to some of the grid rows, and that it consists of several black rectangles not touching each other even with their corners. Follow the input format.

If there are several possible answers, print any of them. It is guaranteed that at least one valid initial table exists.

4 5
..XX.
.XX..
.X...
XX.X.

..XX.
..XX.
X....
X.XX.

4 7
X......
X.....X
..XX..X
..XX...

X......
..XX...
..XX..X
..XX...

3 3
.X.
.X.
.X.

.X.
.X.
.X.

In the first sample case Amir could have chosen rectangles defined by x₁ = 0, y₁ = 0, x₂ = 0, y₂ = 1 and x₁ = 2, y₁ = 2, x₂ = 3, y₂ = 4 that results in a picture shown in the output section. In this case, he should have shifted the second row by 1 position to the left, the third row by 4 positions to the left and the fifth row by 2 positions to the left.

Note that in the second sample case the input picture could not have been drawn by Amir because the cells in the leftmost and the rightmost columns could not have been painted according to Amir's paint procedure.