#74. 徐老师的发财梦

徐老师的发财梦

某天夜里,徐老师做了一个奇妙的梦:他站在一块巨大的方格板前,天空中纷纷掉落金灿灿的金块。这块二维的矩形格子板上,每个格子可能是:

  • '.' 空的;
  • 'g' 表示一块金块(gold);
  • '#' 表示一块神秘的浮空岩石,无法穿透。

在梦里,金块会受重力影响向下掉落——除非下面被岩石或其他金块挡住。

徐老师惊叹于这神奇的景象,他想弄清楚这些金块最终会落在哪里。你能帮他写个程序模拟这个梦境的最终画面吗?

输入格式

输入第一行为两个整数 RC,表示格子的行数和列数:

1 ≤ R ≤ 50000
1 ≤ C ≤ 10

接下来有 R 行,每行 C 个字符,描述这块格子板从上到下的初始状态。每个字符为以下之一:

  • '.' 表示空格;
  • 'g' 表示金块;
  • '#' 表示浮空岩石。

输出格式

输出 R 行,展示所有金块在重力作用下静止后的最终位置。


样例输入 1:

3 3
ggg
#..
..#

样例输出 1:

g..
#.g
.g#

样例输入 2:

4 5
ggg.g
gg.g.
g.g..
...g.

样例输出 2:

.....
g....
gggg.
ggggg