题目描述

译自 CCO 2019 Day1 T2「Sirtet」。

这是一个酷炫的新型无人视频游戏，名为 Sirtet。游戏场地是一个由 $N$ 行 $M$ 列方格组成的矩形网格。游戏开始前，有些格子是空的（用 . 表示），有些格子则被填满（用 # 表示）。填满的格子代表一系列物体，并且水平或垂直相邻的填满格子会被视为同一刚性物体的一部分。例如，如下初始网格：

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

它包含四个物体，如下所示：

##     #     #     #
 ##    #

游戏开始时，所有物体将以相同的速度笔直向下掉落。每个物体一直往下掉，直到它碰到最底一行，或者有一部分正好落在另一个物体的正上方，然后停止下落。最终网格会变成什么样子呢？

输入格式

第一行包含两个空格分隔的正整数 $N,M$。

接下来 $N$ 行，每行包含 $M$ 个字符，描述网格的初始状态。如果网格第 $i$ 行第 $j$ 列包含方块，则输入中对应字符为 #, 否则为 .。

输出格式

输出 $N$ 行，每行包含 $M$ 个字符，描述网格的最终状态。如果网格第 $i$ 行第 $j$ 列包含方块，则输出中对应字符为 #, 否则为 .。

5 4
..#.
##.#
.##.
#...
#...

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

数据范围与提示

对于 $40\%$ 的数据，$N \times M \leq 2000$；
对于另外的 $24\%$ 的数据，$M = 2$；
对于 $100\%$ 的数据，$N \times M \leq 10^6$。