Falling Objects in Sirlet

In the new unmanned game (is it even a game?) Sirlet, the interface is represented by a rectangular grid. At the beginning of the game, some cells are empty (denoted by .) while some are filled (denoted by #). Filled cells that are adjacent (via up, down, left, right connectivity) form a single object.

When the game begins, every object starts to fall downward at the same constant speed. They continue to fall until any cell of the object either touches the bottom row or directly lands on top of a cell belonging to another object. At that moment, the falling of that object stops.

Your task is to simulate this process and output the final state of the grid.

The falling distance for each object is determined as follows. Suppose an object covers several cells. For each cell at position \((i,j)\) of the object, let the falling distance be the minimum non-negative integer \(d\) such that either:

• \(i+d = n-1\) (i.e. it reaches the bottom), or
• There exists some \(p\) with \(i < p \le n-1\) such that the cell \((p,j)\) is filled in the initial grid and it does not belong to the same object, and \(d = p - i - 1\).

The overall falling distance for the object is the minimum falling distance among all its cells. After dropping each object by its computed distance, the final grid is obtained. Note that all objects fall simultaneously.

Input Format: The first line contains two integers \(n\) and \(m\) representing the number of rows and columns. The following \(n\) lines each contain a string of length \(m\) composed only of characters . and #.

Output Format: Output \(n\) lines, each a string of length \(m\), representing the final state of the grid.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) (the number of rows and columns respectively). Each of the next \(n\) lines contains a string of length \(m\) consisting only of characters . and #.

outputFormat

Output \(n\) lines, each containing a string of length \(m\) that represents the final grid after all objects have fallen.

sample

5 4
..#.
##.#
.##.
#...
#...

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