在一个名为 Sirtet 的新颖零玩家电子游戏中，游戏在一个 $N$ 行 $M$ 列的矩形网格中进行。游戏开始前，一些网格单元格是空的（用 . 表示），另一些是填充的（用 # 表示）。填充的方块代表一组物体，彼此相邻（水平或垂直）的填充方块被视为同一个刚体的一部分。例如，以下初始网格：

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

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

##  #  #  #
##     #

当游戏开始时，所有物体以相同的速度垂直向下掉落。每个物体会持续向下掉落，直到它触碰到最底行，或者它的某一部分落在了另一个物体的正上方，此时它会停止运动。网格的最终状态是什么？

输入格式

第一行包含两个用空格分隔的正整数 $N$ 和 $M$ ($N \cdot M \le 10^6$)。

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

数据范围

• 在总共 25 分中，有 10 分满足 $N \cdot M \le 2000$。
• 在总共 25 分中，另有 6 分满足 $M = 2$。

输出格式

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

样例

样例输入 1

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

样例输出 1

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