Under construction

Still being built. Things may change

Meteor

Interview

Time limit1sMemory limit256 MB

Summary
Shift the connected meteor cells straight down until they rest on the ground and print the final grid.
Level

Easy3 of 10

Topics
Simulation, Matrix, Implementation
Solved
No attempts yet

Problem

A photo of a small, oddly shaped meteor appeared online. It shows the meteor in mid air, falling from very high up. The photo taken after the meteor landed was lost, so you have to reconstruct it from the one that remains.

The photo is written as a grid of characters. 'X' is a piece of the meteor, '#' is a piece of the ground, and '.' is air.

All pieces of the meteor are connected. That is, from any meteor cell you can reach any other meteor cell by moving up, down, left, or right through meteor cells only. The ground is connected in the same way.

In the given photo the meteor is above the ground. More precisely, at least one row is made of air only, the meteor is above that row, and the ground is below it. The bottom row of the photo is all ground.

The meteor falls straight down. It moves down one row at a time and stops the moment one more row of movement would put a meteor cell on a ground cell. The meteor and the ground keep their original shapes while it falls. Reconstruct the photo taken after the meteor stopped.

Input

The first line contains the height RR and the width SS of the photo (3≤R,S≤30003 \le R, S \le 3000).

Each of the next RR lines contains the photo as SS characters. Every character is 'X', '#', or '.'.

Output

Print the photo after the meteor stopped, on RR lines of SS characters each.

Examples2

  1. Example 1

    Input
    5 6
.XXXX.
...X..
......
#..###
######
    Expected output
    ......
.XXXX.
...X..
#..###
######

  2. Example 2

    Input
    9 7
XXX.XXX
X.XXX.X
X..X..X
X.....X
.......
.#...#.
.##.##.
.#####.
#######
    Expected output
    .......
.......
.......
.......
XXX.XXX
X#XXX#X
X##X##X
X#####X
#######