题目描述

在一个 $r\times c$ 的方阵里，有些点是 .，表示为空；有些点是 X，表示这里是一堵墙。

我们可以认为这个方阵在竖直方向放置。

有一个人在这 $c$ 列的第一行会抛下 $n$ 块石头，用 O 来表示。如果这一个石头由于重力作用会向下滚动。具体来说，就是会从第一行向最后一行滚动，规则如下：

• 如果下一个格子是空格，那么向下运动一格。
• 如果下一个格子是墙或者已经到了第 $r$ 行，则停止滚动并停在原处。
• 如果下一个格子是一块停止的石头，则如果在左侧和左下方为空格时首选滚动到左侧的那一行，否则如果右侧和右下方为空格，则滚动到右侧的那一行。如果两侧都不为空，则石头静止不在移动。

只有前一块石头永久静止后，下一块石头才会被抛下。

请你输出最终方阵的状态。

输入格式

输入第一行为两个整数 $r,c$。

接下来的 $r$ 行，每行 $c$ 个字符，每个字符可能为 . 或 X。

下一行为一个整数 $n$，表示石头的数量。

接下来的 $n$ 行，每行一个整数 $1\le x\le c$，表示这个石头位于第 $x$ 列被抛下，按照输入顺序依次抛下。

输出格式

输出一个 $r\times c$ 的方阵，包含 . X O，为最终石头都抛完后的状态。

5 4
....
....
X...
....
....
4
1
1
1
1

....
O...
X...
....
OOO.

7 6
......
......
...XX.
......
......
.XX...
......
6
1
4
4
6
4
4

......
...O..
...XX.
......
.OO...
.XX...
O..O.O

提示

样例 1 解释

$4$ 块石头依次在第一列被抛下。第一块石头被唯一一堵墙堵住。这样剩下的石头都可以向右滚动一列。第二块石头毫无障碍地下落，第三四块分别落在了它的左边和右边。

数据规模与约定

• 对于 $60\%$ 的数据，保证 $r\le 30$。
• 对于 $100\%$ 的数据，保证 $1\le r\le 3\times 10^4$，$1\le c\le 30$，$1\le n\le 10^5$。

说明

题目译自 COCI2006-2007 CONTEST #6 T4 KAMEN。