题目描述

小珅最近在一款非常火热的游戏“巨石滚滚”，游戏中某一个关卡难住了小珅。具体来说，该关卡

给定一个 $n\times m$ 的矩阵，矩阵中包含三种类型的单元格：

• 空单元格，用 . 表示；
• 一块巨石，用 * 表示；
• 一个障碍物，用 # 表示。

游戏开始时，所有巨石都会掉落下来（第一行最高，第 n 行最低），直到碰到地板（第 n 行）、障碍物或其他已经无法移动的巨石才会停止掉落。

现在给定矩阵中每个单元格的初始状态，即每个单元格可能为空、有一块巨石或有一个障碍物，请你帮助小珅计算矩阵中所有单元格的最终状态。

输入格式

第一行，两个整数 n,m；

接下来 n 行，每行包含 m 个字符，每个字符都是 .，∗，# 三者之一。

输出格式

n 行，每行包含 m 个字符，每个字符都是 .，∗，# 三者之一，表示矩阵的最终状态。

样例输入

5 5
*****
*....
*****
....*
*****

样例输出

.....
*...*
*****
*****
*****

提示

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

1 1
*

*

1 1 
*

*

2 9
...***###
.*#.*#.*#

....**###
.*#**#.*#