Falling Stones Simulation

You are given an r × c grid. Each cell of the grid is either empty (denoted by a .) or contains a wall (denoted by X). Initially, there are no stones in the grid. A person will drop n stones one by one from the top row at a fixed dropping column. The dropping column is chosen as the middle column of the grid (i.e. column number ⌊c/2⌋, considering 0-indexing).

Each stone behaves according to the following rules under gravity:

• If the cell immediately below the stone is empty (.), the stone falls one cell down.
• If the cell immediately below is a wall (X) or the stone is already at the bottom row, the stone stops moving and remains at its current position.
• If the cell immediately below already contains a stone (O), then the stone will try to roll sideways in the following order:
  • If both the left adjacent cell and the cell diagonally down-left are empty, the stone rolls to the left (i.e. moves to the left cell on the same row) and then continues falling.
  • Otherwise, if both the right adjacent cell and the cell diagonally down-right are empty, it rolls to the right and then continues falling.
  • If neither sideways move is possible, the stone stops moving.

Each stone is dropped only after the previous stone has come to a complete stop. After all stones are dropped and their paths simulated, output the final state of the grid.

inputFormat

The first line contains three integers: r, c, and n (the number of rows, columns, and stones respectively).

Then follow r lines, each containing c characters. Each character is either a . (empty cell) or X (a wall).

outputFormat

Output the final state of the grid as r lines with c characters each. Stones are represented by O.

sample

5 5 3
.....
.....
..X..
.....
.....

.....
..O..
..X..
.....
OO...