You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

给定一个 $n \times m$ 的字符矩阵，其中有一些位置上的字符是 #（代表方块），其他位置是 .（代表空气）。我们将第 $i$ 行第 $j$ 列上的字符定义为 $a_{i, j}$。

apiadu 有一个道具，每次对矩阵使用道具时，会按照以下规则对方阵进行调整： 对于每一个 $1 \le j \le m$（每一列），从下往上依次遍历行 $i$（即 $i$ 从 $n-1$ 递减到 $1$），如果发现 $a_{i, j}$ 是 # 且其下方紧邻的格子 $a_{i+1, j}$ 是 .，则交换 $a_{i, j}$ 与 $a_{i+1, j}$。

apiadu 对这个矩阵使用了 $10^{100}$ 次道具，你需要输出最终矩阵的状态。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，表示矩阵的大小。

接下来的 $n$ 行，每行包含 $m$ 个字符，表示初始矩阵的组成。

输出格式

输出 $n$ 行，每行 $m$ 个字符，表示经过 $10^{100}$ 次操作后的最终矩阵。

样例

样例输入 #1

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

样例输出 #1

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

样例解释 #1

使用一次道具后的矩阵：

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

使用了两次道具后的矩阵：

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

不难发现对这个矩阵再次使用道具不会再使矩阵发生改变。使用 $10^{100}$ 次的效果与使用两次相同。

数据规模

对于 $100\%$ 的数据，$1 \le n, m \le 100$。