Problem K
Falling Apples

The obstacles do not move.

Whenever there is an empty cell immediately below an apple, the apple moves into the empty cell.
Print out the final configuration of the board after all apples reach their final locations. Merely iterating the gravity rule, a step at a time, will likely take too long on large datasets.
Input
The input begins with a line containing integers $R$ and $C$, designating the number of rows and columns of the grid, such that $1 \leq R \leq 50\, 000$ and $1 \leq C \leq 10$. The first line is followed by $R$ additional lines, each designating a row of the grid, from top to bottom. Each line has $C$ characters, each of which is either ’.’, ’a’, or ’#’.
Output
Output $R$ grid lines displaying the final state.
Sample Input 1  Sample Output 1 

3 3 aaa #.. ..# 
a.. #.a .a# 
Sample Input 2  Sample Output 2 

4 5 aaa.a aa.a. a.a.. ...a. 
..... a.... aaaa. aaaaa 