Description

In an $r \times c$ grid, some cells are . meaning empty, and some cells are X meaning there is a wall.

You can think of the grid as being placed vertically.

A person will drop $n$ stones from the first row of one of the $c$ columns. Stones are represented by O. Each stone will roll downward due to gravity, specifically from the first row toward the last row, following these rules:

• If the next cell below is empty, it moves down by one cell.
• If the next cell below is a wall, or it has already reached row $r$, it stops rolling and stays where it is.
• If the next cell below contains a stationary stone, then:
  • If both the left cell and the down-left cell are empty, it will prefer to roll to the left (into the left column).
  • Otherwise, if both the right cell and the down-right cell are empty, it will roll to the right (into the right column).
  • If neither side is possible, the stone becomes stationary and will not move.

Only after the previous stone becomes permanently stationary will the next stone be dropped.

Output the final state of the grid.

Input Format

The first line contains two integers $r, c$.

The next $r$ lines each contain $c$ characters, where each character is either . or X.

The next line contains an integer $n$, the number of stones.

The next $n$ lines each contain an integer $1 \le x \le c$, meaning the stone is dropped in column $x$. Stones are dropped one by one in the input order.

Output Format

Output an $r \times c$ grid containing ., X, and O, representing the final state after all stones have been dropped.

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

Hint

Explanation for Sample 1

$4$ stones are dropped into the first column in order. The first stone is blocked by the only wall. Then the remaining stones can all roll one column to the right. The second stone falls down without any obstacles, and the third and fourth stones land to its left and right respectively.

Constraints

• For $60\%$ of the testdata, $r \le 30$.
• For $100\%$ of the testdata, $1 \le r \le 3 \times 10^4$, $1 \le c \le 30$, $1 \le n \le 10^5$.

Notes

This problem is translated from COCI2006-2007 CONTEST #6 T4 KAMEN。

Translated by ChatGPT 5