Predict the Falling Rocks In this challenge, you are given a map of a two-dimensional terrain, viewed from the side. Unfortunately, some parts of the terrain are floating in the air, which means they'll come crashing down. Your job is to predict where they land.

The Input

Your input is one or more newline-separated strings of equal lengths, containing only the characters # (a number sign, signifying a rock) or . (a period, signifying empty space).

The Output

Your output has the same format as the input, but with the following modification. Let us view the input string as a two-dimensional grid of rocks. Every rock in the input which is connected to the bottom of the grid by a path of adjacent rocks is firm; other rocks are loose. Diagonally adjacent rocks are not considered to be adjacent. All the loose rocks will fall straight down, and end up as a stack on top of either a firm rock or the bottom row. The loose rocks are not attached to each other, so they fall individually, not as big formations. The output is the resulting grid.

Examples


The input

..###.
.##.#.
.#....
.##.#.


contains no loose rocks, so the output is identical to it.
The input

...#..
.#..#.
.#..##
.#...#
.#####
.#...#


contains one loose rock at the top, which falls down on the firm rock under it. The output is

......
.#..#.
.#..##
.#.#.#
.#####
.#...#

The input

.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#


has a large group of loose rocks on the left. The group breaks down as the rocks fall, so the output is

..........
....######
..#.###..#
. #...##..
.##....#..
.##...####
####..#..#
#####.#..#



Clarifications


You can either take the input from STDIN and output to STDOUT, or write a function.
This is code-golf, so shortest program (in bytes) is the winner.
Standard loopholes are disallowed.
Perl 5: 98

98 including 2 command line flags.

#!perl -p0
1while/
/,($x="($`)")=~y!#!.!,s/#(.*
$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;1while s/#$x\./.$1#/s;y!%!#!


Explanation:

#!perl -p0 #read entire input to $_ and print at the end
/\n/;($x="($`)")=~y!#!.!; #calculate pattern matching space
                          #between two characters in the same column
                          #looks like "(......)" 
1 while s/#(.*\n$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;
                          #flood fill solid rock with %
1 while s/#$x\./.$1#/s;   #drop loose rock
y!%!#!                    #change % back to #