Problem G
Falling Snow
Princess Kaguya is running through the snowy mountains! However, since it has been snowing quite hard, the terrain is very rough, and thus she would like to plan around it.
Kaguya has created a mental image of what the snow was like some time ago, which may include snow suspended in the air. More formally, she envisions a grid of dimension $N$ by $M$, where the symbol ‘S’ represents snow and periods represent nothingness.
All snow will fall directly downwards in the grid at the same speed, until it hits another piece of snow or the bottom of the grid, and then it will stay there.
Given the original configuration of the snow, help Kaguya figure out what the snow looks like after it all falls!
Input
The first line contains two integers, denoting the number of rows in the grid $N \: (1 \leq N \leq 100)$, and the number of columns in the grid $M \: (1 \leq M \leq 100)$.
Then, $N$ lines follow, where each line is a string of length $M$, where each character is either a period ‘.’ or the capital letter ‘S’. A period ‘.’ represents nothingness, and the letter ‘S’ represents snow.
Output
Output a grid of size $N$ by $M$ characters, representing the final configuration of the grid. This output grid should also only consist of periods ‘.’ and the capital letter ‘S’.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 S.S S.. .S. ..S |
... ... S.S SSS |
