题目描述

你需要复原一幅流星坠落后的照片。

流星坠落前的照片可以被看作是一个 $R\times S$ 的字符矩阵。$\texttt X$ 表示流星的一部分，$\texttt \#$ 表示地面，其他部分是空气，用 $\texttt .$ 表示。所有 $\texttt X$ 是联通的。

注意到流星严格位于地面上方，即存在一行 $\texttt .$ 使得 $\texttt X$ 都在它上方且 $\texttt \#$ 都在它下方。照片最后一行必定都是 $\texttt \#$。

请还原出流星落地后的照片，落地后流星与地面性质都未改变。

输入格式

第一行两个整数 $R,S$。

接下来 $R$ 行每行一个长度为 $S$ 的字符串，表示这个流星坠落前的照片。

输出格式

一个 $R\times S$ 的矩阵，表示你还原的流星坠落后的照片。

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
#######

提示

数据规模与约定

对于 $100\%$ 的数据，有 $3\le R,S\le 3\times 10^3$，字符矩阵中的字符都是 $\texttt{X \# .}$ 中的一种。

说明

按原题配置，满分 100 分。

译自 COCI 2014-2015 Contest #6 Task C METEOR。