现有一面墙，可以看作 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 的字符串，表示足够长的时间之后的网格，输出格式同题目描述。

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

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

- 特殊性质 1：保证没有挡板。

- 特殊性质 2：保证箱子只有 `A`。

其中20%的数据：符合特殊性质1和2，且n=1;

另外有20%的数据：符合特殊性质2，且n=1;

另外有20%的数据：符合特殊性质1，且6\leq n \leq 10;

另外有40%的数据：6\leq n \leq 10^5,m\leq 10;

---

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