题目描述

工程师千夏正在模拟一个二维重力场。给定一个 $N\times M$ 的二值矩阵。字符 . 表示空格，字符 # 表示该格被某个方块占据。

所有由 # 组成的极大四连通块都视为一个不可分割的物体。四连通指通过上下左右相邻连接。在下面的下落过程中，物体不会合并，也不会分裂；同一个物体中的所有格子始终以完全相同的方式移动。

所有物体同时开始向地板方向下落，地板是矩阵的最后一行。物体只会竖直向下移动，不会旋转。每一秒，所有仍在运动的物体都尝试向下移动一行：

• 如果某个物体这样移动后会越过矩阵下边界，那么它停止在原位；
• 如果某个物体这样移动后会与另一个物体重叠，那么它也停止在原位。注意，这种重叠只可能发生在下方那个物体已经停止时。

换句话说，物体在碰到地板或碰到已经停止的物体时停止下落。

请输出所有物体停止后的最终矩阵。

输入格式

第一行包含两个整数 $N,M$，表示矩阵大小。

接下来 $N$ 行，每行包含 $M$ 个字符，字符为 . 或 #，表示初始矩阵。每行字符之间没有空格。

输出格式

输出最终矩阵。格式与输入中的矩阵相同，但不需要输出矩阵尺寸。

数据范围

• $1\le N,M\le 2000$。

样例 1

输入

10 10
..........
..######..
..#....#..
..#.#..#..
..#..#.#..
..#....#..
..######..
..........
..#....#..
.......#..

输出

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