Description

Two groups of cavemen have a land dispute and decide to settle it the old way—by throwing sticks at each other. The fight takes place inside a cave. The cave is very tall, so there is no need to worry about sticks flying too high, but the minerals on the ground will obstruct the sticks.

The cave can be divided into $r$ rows and $c$ columns, so the whole cave consists of $r \times c$ cells (it can be seen as a vertical plane).

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

At the start of the fight, one group of cavemen is on the left side of the cave, and the other group is on the right side. The two groups take turns throwing sticks at the other group. First, the throwing group chooses the height at which the stick will fly, and then (if necessary, climbing onto someone’s shoulders) throws it. The stick will fly horizontally through the cave at the chosen height.

If the stick hits a mineral block along the way, the mineral block in that cell will be destroyed (i.e., it no longer exists), and the stick will also fall to the ground and stop flying.

After a mineral block is destroyed, the mineral cluster connected to it may lose its support and fall toward the ground due to gravity. During the fall, the mineral cluster does not change shape, meaning all blocks in it fall together. If, during falling, any mineral block touches the ground, the whole cluster stops falling and becomes a newly formed mineral block. In particular, if a mineral block lands on another mineral block, they will merge into one mineral block.

Given the initial layout of mineral blocks in the cave and the throwing heights of the sticks, determine the mineral layout inside the cave after the fight ends.

Input Format

The first line contains two integers $r$, $c$, as described above.

The next part is a character grid 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, the throwing heights of the sticks. Height $1$ is the bottom of the grid, and height $r$ is 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 with $c$ characters, representing the final layout of the cave.

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

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

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

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

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

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

Hint

Explanation for Sample #2

The first stick destroys the mineral block at column $4$ and height $6$, and no mineral blocks lose support and fall.

The second stick destroys the mineral block at column $7$ and height $6$, and no mineral blocks lose support and fall.

The third stick destroys the mineral block at column $3$ and height $4$, causing the two mineral blocks at column $4$ and heights $4$ and $5$ to fall until they merge with the mineral block at column $4$ and height $1$.

The fourth stick destroys the mineral block at column $7$ and height $3$, causing the mineral block at column $6$ and height $3$, together with the mineral blocks at column $5$ and heights $3$, $4$, $5$, and the mineral block at column $6$ and height $6$, to fall together until they reach the ground.

The fifth stick destroys the mineral block at column $2$ and height $1$, and no mineral blocks lose support and fall.

Constraints

• For $100\%$ of the testdata, $1\le r,c,n \le 100$.
• For $100\%$ of the testdata, it is guaranteed that in the initial state, no cluster is floating in the air, and at any time, there will not be two or more clusters falling at the same time.

Notes

• This problem is worth $120$ points.
• This problem is translated from COCI2008-2009 CRCI2008-2009 RELJEF. The main translation work was done by
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5