Mineral Clash

Two groups of cavemen are in a dispute over land and decide to settle it the old-fashioned way—by throwing sticks at each other. The battle takes place in a cave which is divided into \(r\) rows and \(c\) columns, forming a vertical grid. Each cell in the grid is either empty or contains a mineral rock. Two rocks belong to the same mineral cluster if they are adjacent in one of the four cardinal directions (up, down, left, right).

The cavemen stand on opposite sides of the cave: one group on the left and the other on the right. They take turns throwing sticks horizontally at a specified height. The first throw comes from the left and the direction alternates thereafter. When a stick is thrown, it travels across the cave at the chosen height. If it hits a mineral rock along the way, that rock is destroyed and the stick falls, ending its flight.

After a rock is destroyed, some mineral clusters may lose their support. A cluster is supported if at least one of its rocks is connected (via adjacent rocks) to the ground (i.e. the bottom row). Any unsupported (floating) cluster falls down as a whole, maintaining its shape. It falls until at least one rock in the cluster would land on the ground or on top of another rock. In the latter case, the falling cluster merges with the rock that it lands on.

Your task is to simulate the battle. Given the cave layout and the sequence of throw heights, determine the final configuration of minerals inside the cave.

The cave grid is indexed from the top (row 0) to the bottom (row \(r-1\)). Note that the throw height is given with respect to the bottom: a throw height of \(h\) corresponds to row \(r - h\) in the grid.

inputFormat

The first line contains two integers \(r\) and \(c\) (the number of rows and columns).

The next \(r\) lines each contain a string of length \(c\) representing the cave grid. A '.' indicates an empty cell, and an 'x' indicates a mineral rock. The first of these \(r\) lines corresponds to the top row.

The following line contains an integer \(n\), the number of throws.

The last line contains \(n\) integers representing the heights at which the sticks are thrown. A height \(h\) means the stick travels in row \(r-h\). The first throw is made from the left, the second from the right, and so on, alternating directions.

outputFormat

Output the final cave layout after all throws. Print \(r\) lines, each containing a string of length \(c\). The first line corresponds to the top row of the cave.

sample

5 6
......
..xx..
..xx..
.xxxx.
xxxxxx
3
3 4 2

......
......
..xx..
..xxx.
xxxxxx