Gravity

Interview

Time limit1sMemory limit512 MB

Summary

Apples fall straight down until they rest on obstacles or the floor; print the final grid.

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

Problem

Simulate gravity on a two-dimensional grid of $n$ rows and $m$ columns.

Each cell holds an obstacle, holds a single apple, or is empty.

Apply the following rules until no further change is possible.

Obstacles never move.
If the cell immediately below an apple is empty, the apple moves into that cell.

Find the state of the grid after every apple has settled.

Input

The first line contains two integers $n$ and $m$ separated by a space. ( $1 \le n, m \le 50$ )

Each of the next $n$ lines contains $m$ characters describing one row of the grid, from top to bottom. An obstacle is #, an apple is o, and an empty cell is ..

Output

Print the state of the grid on $n$ lines after all of the rules above have been applied.

Examples2

Example 1
Input
```
3 3
ooo
#..
..#
```
Expected output
```
o..
#.o
.o#
```
Example 2
Input
```
4 2
oo
oo
o.
..
```
Expected output
```
..
o.
oo
oo
```