For nearly two weeks now, Domeniko has been lying in his bed because his friend Nedjeljko accidentally threw a large rock on his left foot. As Domeniko has already solved the tasks from all Croatian national competitions since 1998, he has to find a new way to kill time.

Domeniko's new game is played on an \(R \times C\) board. Initially, every square is either empty or blocked by a wall. Domeniko throws a rock into the board by putting it in the topmost row of a column and then letting gravity do the rest.

Gravity works as follows:

• If the square under the rock is a wall or if the rock is in the bottom row of a column, then the rock remains there.
• If the square under the rock is empty, then the rock moves to that square.
• If the square under the rock contains another rock, then the falling rock may slide sideways:
  • If the squares left and left-down of the rock are empty, then the rock slides one square left.
  • If the rock doesn't slide left and the squares to the right and right-down are empty, then the rock slides one square right.
  • Otherwise, the rock remains there and never moves again.

Domeniko will never throw another rock while the previous rock hasn't settled down.

Write a program that draws the board after Domeniko throws all his rocks into the board, if we know the columns that Domeniko threw his rocks into, in order.

Note: Domeniko will never throw a rock into a column in which the top row isn't empty.

The first line contains integers \(R\) and \(C\) (\(1 \le R, C \le 100\)), the size of the board.

Each of the following \(R\) lines contains \(C\) characters, the initial layout of the board. A . represents an empty field, while the uppercase letter X is a square blocked by a wall.

The next line contains an integer \(M\) (\(1 \le M \le 100\,000\)), the number of rocks.

Each of the following \(M\) lines contains an integer between \(1\) and \(C\), the column into which Domeniko throws a rock (the leftmost column is column \(1\)).

Note: In \(50\%\) of the test cases, \(M\) will be no more than \(1\,000\).

Output \(R\) lines, each containing \(C\) characters, the final layout of the board. Rocks should be presented with an uppercase letter O.

riseoj 작성

출처 COCI 2006/2007 Contest 6