Canadian Computing Olympiad: 2019 Day 1, Problem 2

In a fancy new zero-person video game, Sirtet, the game is a rectangular grid with ~N~ rows and ~M~ columns. Before the game begins, some grid cells are blank (denoted as .) and others are filled (denoted as #). The filled squares represent a set of objects, and the filled squares that are adjacent (horizontally or vertically) should be considered to be part of 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 continues to fall straight down until it either touches the bottom row, or has some part of it land directly on top of another object, at which point it stops. What will be the final state of the grid?

Input Specification

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 of the grid contains a block, the corresponding character in the input will be a #, otherwise it will be a . character.

For 10 of the 25 available marks, ~N \cdot M \le 2000~.

For an additional 6 of the 25 available marks, ~M = 2~.

Output Specification

Output ~N~ lines contain ~M~ characters each, describing the final state of the grid. If the ~j~-th column of the ~i~-th row of the grid contains a block, the corresponding character in the input will be a #, otherwise it will be a . character.

Sample Input

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

Output for Sample Input

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