Description

In a new kind of unattended game (does this even count as a game) called Sirlet, the screen is a rectangular grid. Before the game starts, some cells are empty (shown as .), and some cells are filled (shown as #). The filled cells represent a set of objects, and adjacent filled cells are considered to be the same object.

For example, this initial grid:

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

contains the following 4 objects:

##   #  #  #
 ##  #

When the game starts, each object begins to fall downward at the same constant speed. They keep falling until they touch the bottom row or the top of another object, and then stop falling at the moment of contact.

Find the final state of the grid.

Input Format

The first line contains two positive integers $N$ and $M$ (separated by a space).

The next $N$ lines each contain $M$ characters representing the grid. Each character is either # or ., with meanings as described above.

Output Format

Output $N$ lines, each containing $M$ characters representing the final state of the grid. Each character is either # or ., with meanings as described above.

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

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

Hint

Constraints

$1 \le N \times M \le 10^6$

Subtasks

Subtask 1 (40 points): $1 \le N \times M \le 2000$

Subtask 2 (24 points): $M = 2$

Subtask 3 (36 points): No additional constraints.

Translated by ChatGPT 5