题目描述

在一款新型的无人游戏（话说这算游戏吗）Sirlet中，界面是一个矩形网格。在游戏开始之前，一些方格是空白的（表示为.），而一些方格是被填充的（表示为#）。那些被填充的方格代表一组物体，而相邻的被填充方格被视作同一物体。

例如，这个初始网格：

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

包含以下4个物体：

##   #  #  #
 ##  #

当游戏开始时，每个物体开始以相同的速度匀速下落，它们持续下落，直到它接触到最下面的一行或是另一物体的顶部，而在接触时停止下落。

求网格的最终状态。

输入格式

第一行，两个正整数$N M$（用空格隔开）。

随后$N$行，每行$M$个字符，代表网格。它们或是#，或是.，含义见题目描述。

输出格式

$N$行，每行$M$个字符，代表网格的最终状态。它们或是#，或是.，含义见题目描述。

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

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

提示

限制

$1 \le N \times M \le 10^6$

子任务

Subtask 1 （40分）：$1 \le N \times M \le 2000$

Subtask 2 （24分）：$M = 2$

Subtask 3 （36分）：没有附加限制。