题目描述

现有一面墙，可以看作 $n$ 行 $m$ 列的网格，其中从上往下第 $i$ 行、从左到右第 $j$ 列的格子记为 $(i,j)$。

每个格子可能有一个箱子、一块挡板，或者没有东西。箱子有 $26$ 种（未必只有 $26$ 个），用大写字母标号。

具体地，我们使用一个字符数组 $a_{i,j}$ 来表示这个网格，其中：

• $a_{i,j}$ 是大写字母时表示 $(i,j)$ 是一个标号为 $a_{i,j}$ 的箱子。
• $a_{i,j}$ 是减号 - 时表示 $(i,j)$ 是一块挡板。
• $a_{i,j}$ 是句点 . 时表示 $(i,j)$ 没有东西。

由于重力原因，在任意时刻，如果一个在 $(i,j)$ 的箱子下方格子（即 $(i+1,j)$）存在并且没有东西，那么它会下落到这个格子。

给出初始时每个格子上的情况，输出经过足够长的时间后每个格子的情况。

输入格式

第一行有两个正整数 $n,m$，表示网格的行数和列数。

之后有 $n$ 行，每行有一个长为 $m$ 的字符串，表示这个网格 $a_{i,j}$，具体含义同题目描述。

输出格式

输出 $n$ 行，每行有一个长为 $m$ 的字符串，表示足够长的时间之后的网格，输出格式同题目描述。

6 3
A.B
...
..-
..D
C..
...

...
..B
..-
...
A..
C.D

提示

【数据范围】

对于全部数据，保证 $1\le n\le 10^5$，$1\le m\le 10$，$a_{i,j}$ 只可能是 .，- 或大写字母。

本题共有 $10$ 个测试点，部分测试点有特殊限制，具体如下：

测试点编号	$n\le$	特殊性质
$1$	$200$	1,2
$2,3$		1
$4$		2
$5,6$
$7$	$10^5$	1,2
$8$		1
$9$		2
$10$

其中：

• 特殊性质 1：保证没有挡板。
• 特殊性质 2：保证箱子只有 A。

---

提示：从下往上依次考虑每一个箱子的最终位置，就可以保证每个箱子落地后一定不再移动。