给定一个 $N \times M$ 的二进制矩阵。单元格 $(i, j)$ 如果为空，则包含字符 “.”；如果被碎片占据，则包含字符 “#”。每个由 “#” 字符构成的极大 4-连通分量形成一个不可分割的碎片。在下述过程中，碎片不会以任何方式合并或分裂。属于同一个碎片的所有单元格将以完全相同的方式移动。

碎片开始以相同的速度向地面（矩阵的最后一行）下落。碎片在下落过程中不会发生旋转。每一秒，所有碎片都会尝试向下移动一行。如果这种移动导致碎片越过矩阵的下边界，该碎片将停留在原位。同样，如果这种移动导致碎片与另一个碎片重叠（注意，这种情况仅在后者未移动时发生），则前者也会停留在原位。换句话说，当碎片撞击地面或撞击另一个碎片时，它们会停止下落。

输出所有碎片停止下落后的最终状态。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 2000$)。

接下来的 $N$ 行描述了该矩阵。每一行包含 $M$ 个字符，均为 “.” 或 “#”。同一行中表示单元格的字符之间没有空格。

输出格式

打印所有碎片停止下落后的结果矩阵。除了包含矩阵尺寸的那一行外，矩阵的打印格式应与输入格式相同。

样例

输入格式 1

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

输出格式 1

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