Problem Description

Two groups of cave dwellers are in a land dispute and have decided to resolve it the old way—by throwing sticks at each other. The conflict takes place in a cave, which is so high that there's no need to worry about the sticks flying too high, but the minerals on the ground can hinder the flight of the sticks.

The cave can be divided into $r$ rows and $c$ columns, making up a total of $r \times c$ cells (which can be considered as a vertical plane).

Each cell in the cave is either empty or contains a mineral block. If two mineral blocks are adjacent in one of the four main directions (up, down, left, right), they are considered part of the same mineral cluster.

At the start of the conflict, one group of cave dwellers is on the left side of the cave, and the other group is on the right side. They take turns throwing sticks at each other, with one group choosing the height at which the stick will fly horizontally across the cave.

If a stick hits a mineral block, that block is destroyed (it no longer exists), and the stick falls to the ground, stopping its flight.

When a mineral block is destroyed, the mineral cluster it was part of may fall due to gravity if there are no remaining blocks to support it. The falling cluster does not change shape, meaning all blocks in the cluster fall together. If a block in the cluster lands on the ground, the entire cluster stops falling and becomes a new mineral block. Specifically, if a block lands on another block, they merge into one block.

Given the initial layout of mineral blocks in the cave and the heights at which the sticks are thrown, determine the final layout of the cave after the conflict.

Input Format

The first line contains two integers $r$ and $c$, as described in the problem.

Next is a character table with $r$ rows and $c$ columns. . represents an empty cell, and x represents a cell containing a mineral block.

The next line contains a positive integer $n$, the number of sticks.

The last line contains $n$ integers, representing the heights at which the sticks are thrown. Height $1$ is at the bottom of the matrix, and height $r$ is at the top. The first stick flies from left to right, the second from right to left, and so on.

Output Format

Output $r$ lines, each containing $c$ characters, representing the final layout of the cave.

Sample Input and Output

Sample Input #1

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

Sample Output #1

......
......
..xx..
..xx..
.xxxx.

Sample Input #2

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

Sample Output #2

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

Sample Input #3

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4

Sample Output #3

......
......
......
......
..xx..
xx.xx.
.x..x.

Notes/Hints

Sample #2 Explanation

• The first stick destroys the mineral block at column $4$, height $6$, without causing any other blocks to fall.
• The second stick destroys the mineral block at column $7$, height $6$, without causing any other blocks to fall.
• The third stick destroys the mineral block at column $3$, height $4$, causing the blocks at column $4$, heights $4$ and $5$, to fall and merge with the block at height $1$.
• The fourth stick destroys the mineral block at column $7$, height $3$, causing the block at column $6$, height $3$, along with the blocks at column $5$, heights $3$, $4$, and $5$, and the block at column $6$, height $6$, to fall to the ground.
• The fifth stick destroys the mineral block at column $2$, height $1$, without causing any other blocks to fall.

Data Constraints

• For $100\%$ of the data, $1 \le r, c, n \le 100$.
• For $100\%$ of the data, it is guaranteed that no mineral cluster will be floating in the air initially, and at no point will there be two or more clusters falling simultaneously.

Notes

• This problem is worth $120$ points.
• This problem is translated from COCI2008-2009 CRCI2008-2009 RELJEF, with primary translation work by @tearing and polishing by @mnesia, including the translation of the explanation for Sample #2.

见题面 Input 部分

见题面 Output 部分