Kamen

친구 Nedjeljko가 실수로 왼발에 큰 돌을 떨어뜨리는 바람에, Domeniko는 벌써 2주 가까이 침대에 누워 있다. 1998년 이후의 크로아티아 전국 대회 문제를 이미 다 풀어 버린 Domeniko는 시간을 때울 새로운 방법을 찾아야 한다.

Domeniko의 새 게임은 \(R \times C\) 보드에서 진행된다. 처음에 각 칸은 비어 있거나 벽으로 막혀 있다. Domeniko는 어떤 열의 맨 윗줄에 돌을 놓고, 나머지는 중력에 맡기는 방식으로 보드에 돌을 던진다.

중력은 다음과 같이 작용한다:

• 돌 아래 칸이 벽이거나 돌이 열의 맨 아랫줄에 있으면, 돌은 그 자리에 머문다.
• 돌 아래 칸이 비어 있으면, 돌은 그 칸으로 이동한다.
• 돌 아래 칸에 다른 돌이 있으면, 떨어지던 돌은 옆으로 미끄러질 수 있다:
  • 돌의 왼쪽 칸과 왼쪽 아래 칸이 비어 있으면, 돌은 왼쪽으로 한 칸 미끄러진다.
  • 왼쪽으로 미끄러지지 않았고 오른쪽 칸과 오른쪽 아래 칸이 비어 있으면, 돌은 오른쪽으로 한 칸 미끄러진다.
  • 그렇지 않으면 돌은 그 자리에 머물며 다시는 움직이지 않는다.

Domeniko는 이전 돌이 자리를 잡기 전에는 절대 다음 돌을 던지지 않는다.

Domeniko가 돌을 던진 열들이 순서대로 주어졌을 때, 모든 돌을 던진 뒤의 보드를 그리는 프로그램을 작성하시오.

참고: Domeniko는 맨 윗줄이 비어 있지 않은 열에는 절대 돌을 던지지 않는다.

첫째 줄에 보드의 크기인 정수 \(R\)과 \(C\) (\(1 \le R, C \le 100\))가 주어진다.

다음 \(R\)개의 줄에는 \(C\)개의 문자가 주어진다. 보드의 초기 배치이다. .은 빈 칸을 나타내고, 대문자 X는 벽으로 막힌 칸이다.

다음 줄에 돌의 개수인 정수 \(M\) (\(1 \le M \le 100\,000\))이 주어진다.

다음 \(M\)개의 줄에는 \(1\) 이상 \(C\) 이하의 정수가 주어진다. Domeniko가 돌을 던지는 열이다(가장 왼쪽 열이 열 \(1\)이다).

참고: 전체 테스트 케이스의 \(50\%\)에서는 \(M\)이 \(1\,000\) 이하이다.

각각 \(C\)개의 문자로 이루어진 \(R\)개의 줄을 출력한다. 보드의 최종 배치이다. 돌은 대문자 O로 나타내야 한다.

riseoj 작성

출처 COCI 2006/2007 Contest 6