Falling Apples

Interview

Time limit5sMemory limit512 MB

Summary

Let apples fall under gravity in a grid with fixed obstacles until none can move, then print the final grid.

Level: Medium4 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

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.

Input

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

Output

Print the final state of the grid on R lines.

Examples2

Example 1
Input
```
3 3
aaa
#..
..#
```
Expected output
```
a..
#.a
.a#
```

Example 2

Input

4 5
aaa.a
aa.a.
a.a..
...a.

Expected output

.....
a....
aaaa.
aaaaa