Gravity

You are given an $N \times M$ binary matrix. Cell $(i, j)$ is free if it holds the character ., and occupied by a piece if it holds the character #. Each maximal 4-connected group of # cells forms one piece. Pieces are indivisible. During the process below, pieces never merge or split. All cells of the same piece move together.

All pieces start falling toward the floor (the last row) at the same speed. Pieces move straight down without rotating. Every second, every piece tries to move down one row. If the move would take a piece past the lower boundary, that piece stops in place. If the move would make a piece overlap another piece, the moving piece stops in place. This overlap can only happen when the other piece is not moving. In short, a piece stops when it reaches the floor or hits another piece.

Print the final state of the matrix after all pieces have stopped.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 2000$). Each of the next $N$ lines contains $M$ characters, each either . or #. Characters on the same line are not separated by spaces.

Print the matrix after all pieces have stopped, in the same format as the input, except without the line with the dimensions.