P5532 [CCO 2019] Sirtet

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.

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 $N$ lines, each containing $M$ characters representing the final state of the grid. Each character is either `#` or `.`, with meanings as described above.

### 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