game-of-cubes-43

Alice and Bob are playing a game. In this game small cubes are placed over each other, forming a cuboid of length B, height L and breadth 1. 
The special property in these cubes is that adjacent cubes always form a cluster. For example,  
 
This denotes are cuboid of L=4, B=5. 'x' denote the small cubes. '.' means empty space.
In this matrix, the rows are numbered 1 to L from bottom to up, and columns are numbered 1 to B from left to right.
Note that a cluster requires a support, otherwise due to gravity it will fall down. Example, this state is not possible:  
Due to gravity, this cluster will settle down, to reach a stable state like this:     
Another example:    
The above configuration will stabilise to:       
So, a cluster not having support will fall down due to gravity. While falling, it would not change it's shape. If any cube in this cluster comes in contact with cube from another cluster or ground, it will stop falling.    

Now the game is as follows:    
Alice and Bob alternate turns, Alice starting first. In each move of his/hers, the player would choose a height and throw an arrow. Alice throws from left to right, and Bob from right to left. If the arrow hits a cube, the cube and arrow both will be destroyed. If due to destruction of a cube, the cuboid becomes unstable, it will stabilise on it's own.         

Example:    
If current state was this,   
If Alice throws an arrow at height 3, the cube at (3,3) will be destroyed, intermediate situation will be this: 
which will settle down to:  
Given the moves of Alice and Bob, can you print the final state of the cuboid.    
Note that, the testdata is such that, at any point of time, no two clusters will be falling at the same time. Also, initially, the cuboid is in the stable state.       

Input: 
First line contains two space separated integers denoting L and B.  
Each of the next L lines contain B characters each.
Each character is either 'x' or '.' , denoting the presence or absence of a cube at that position.   
Next line contains N, the number of moves.   
Next line contains N integers, each integer denoting a height at which the arrow was thrown.

The moves are alternative, first move being made by Alice.       

Output: 
Print the final state of the cuboid.

Constraints:    
1 ≤ L,B ≤ 100
1 ≤ N ≤ 100

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

SAMPLE OUTPUT
......
......
..xx..
..xx..
.xxxx.

Source: hackerearth | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions: