Mineral Clusters

Changyoung and Sanggeun are arguing over ownership of a cave. They decide to settle it by taking turns throwing sticks inside the cave. The cave contains minerals, and a stick can destroy a mineral when it hits one.

The cave is represented as an R by C grid. Each cell is either empty or contains a mineral. Mineral cells that are adjacent vertically or horizontally belong to the same cluster.

Changyoung stands on the left side of the cave, and Sanggeun stands on the right side. They throw sticks in alternating turns. Each stick flies horizontally at the chosen height. The first turn is thrown from left to right, the second from right to left, and the direction keeps alternating. When the stick first meets a mineral, that mineral is destroyed and the stick stops there.

After a mineral is destroyed, an existing cluster may split. If a newly separated cluster is floating in the air, gravity makes it fall. The cluster keeps its shape while falling and moves down until it is just above the floor or another mineral cluster. After it lands, it becomes connected with the cluster it touches.

Given the initial cave and the heights of all throws, compute the cave after every stick has been thrown.

The first line contains R and C, the size of the cave. (1 <= R, C <= 100)

The next R lines describe the cave from top to bottom. Each line contains C characters: . for an empty cell and x for a mineral.

The next line contains N, the number of sticks thrown. (1 <= N <= 100)

The last line contains N heights separated by spaces. Every height is between 1 and R. Height 1 is the bottom row, and height R is the top row. The first stick is thrown from left to right, the second from right to left, and the direction alternates afterward.

Initially, no mineral cluster is floating. After a single mineral is destroyed, the input never causes two or more clusters to fall at the same time. Whenever a cluster falls, at least one lowest mineral of the cluster in some column lands directly on the floor or on another mineral.

Print the cave after all sticks have been thrown, using the same grid format as the input.