Problem Description

You need to restore a photo after a meteor has fallen.

The photo before the meteor falls can be seen as an $R \times S$ character matrix. $\texttt X$ represents part of the meteor, $\texttt \#$ represents the ground, and the other parts are air, denoted by $\texttt .$. All $\texttt X$ cells are connected.

Note that the meteor is strictly above the ground. That is, there exists a row of $\texttt .$ such that all $\texttt X$ are above it and all $\texttt \#$ are below it. The last row of the photo is guaranteed to be all $\texttt \#$.

Please output the photo after the meteor lands. After landing, neither the meteor nor the ground changes its properties.

Input Format

The first line contains two integers $R, S$.

The next $R$ lines each contain a string of length $S$, describing the photo before the meteor falls.

Output Format

Output an $R \times S$ matrix, representing the restored photo after the meteor falls.

5 6
.XXXX.
...X..
......
#..###
######

......
.XXXX.
...X..
#..###
######

9 7
XXX.XXX
X.XXX.X
X..X..X
X.....X
.......
.#...#.
.##.##.
.#####.
#######

.......
.......
.......
.......
XXX.XXX
X#XXX#X
X##X##X
X#####X
#######

Hint

Constraints

For $100\%$ of the testdata, $3 \le R, S \le 3 \times 10^3$, and each character in the matrix is one of $\texttt{X \# .}$.

Notes

According to the original problem settings, the full score is 100 points.

Translated from COCI 2014-2015 Contest #6 Task C METEOR.

Translated by ChatGPT 5