Falling Apples

You have a rectangular grid with R rows and C columns. Every cell is empty, holds an apple, or holds an obstacle. An empty cell is written as ., an apple as a, and an obstacle as #.

Apply gravity by these rules.

• Obstacles never move.
• If the cell directly below an apple is empty, that apple moves down into it.

Apply the rules until no apple can move any further, then print the final state of the grid. Stepping the rule one cell at a time is too slow for the largest inputs.

The first line contains the number of rows R and the number of columns C of the grid ($1 \le R \le 50\,000$, $1 \le C \le 10$).

Each of the next R lines gives one row of the grid, from top to bottom. Every line holds C characters, each of which is ., a, or #.

Print the final state of the grid on R lines.