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

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

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

输入格式

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

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

输出格式

打印所有碎片停止下落后的最终矩阵。输出格式必须与输入格式相同，但不需要包含矩阵维度的行。

样例

输入 1

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

输出 1

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