Sirtet

In the zero-player video game Sirtet, the game takes place on a rectangular grid with $N$ rows and $M$ columns. Before the game begins, some cells are blank (.) and others are filled (#). Filled cells that are adjacent horizontally or vertically belong to the same rigid object. For example, this initial grid:

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

has four objects, shown below:

##     #    #     #
 ##    #           

When the game begins, the objects fall straight down the grid, all at the same speed. Each object keeps falling until it either touches the bottom row or has some part land directly on top of another object, at which point it stops. What will be the final state of the grid?

The first line contains two space-separated positive integers $N$ and $M$ ($N \cdot M \le 10^6$).

The following $N$ lines contain $M$ characters each, describing the initial state of the grid. If the $j$-th column of the $i$-th row contains a block, the corresponding character is #. Otherwise it is ..

Output $N$ lines of $M$ characters each, describing the final state of the grid. If the $j$-th column of the $i$-th row contains a block, the corresponding character is #. Otherwise it is ..