Bomberman 2

Bomberman lives on a rectangular grid of size R×C. Each cell of the grid is either empty or contains a bomb.

A cell with a bomb explodes after 3 seconds. After a bomb explodes, the cell it occupied is destroyed and becomes empty, and the four adjacent cells are destroyed as well. That is, if the cell with the bomb is (i, j), then (i+1, j), (i-1, j), (i, j+1), and (i, j-1) are destroyed too. If an adjacent cell contains a bomb when a bomb explodes, that adjacent bomb is destroyed without exploding. Therefore, there is no chain reaction.

Bomberman is immune to bombs, so he can move freely to any cell of the grid. Bomberman acts as follows.

• At the very beginning, Bomberman places bombs on some cells. All bombs are placed at the same time.
• For the next 1 second, Bomberman does nothing.
• For the next 1 second, he places a bomb on every cell that does not already contain a bomb. That is, every cell then contains a bomb. All bombs are assumed to be placed simultaneously.
• After 1 second passes, all bombs placed 3 seconds earlier explode.
• Steps 3 and 4 repeat.

Given the initial state in which bombs have been placed, find the state of the grid after N seconds.

For example, consider the case where the initial state is as follows.

...
.O.
...

After 1 second nothing happens, so the grid is the same as above. After 1 more second, the state of the grid is as follows.

OOO
OOO
OOO

After 1 more second, the bomb in the middle explodes, and the middle cell and the four adjacent cells become empty.

O.O
...
O.O

The first line gives R, C, N (1 ≤ R, C ≤ 200, 1 ≤ N ≤ 10^9). From the second line, R lines give the initial state of the grid. An empty cell is given as '.' and a bomb as 'O'.

Print the state of the grid after N seconds in R lines.

Below are the states of the example grid as time passes.

.......
...O...
....O..
.......
OO.....
OO.....

<initial state, after 1 second>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<after 2 seconds>

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

<after 3 seconds>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<after 4 seconds>

.......
...O...
....O..
.......
OO.....
OO.....

<after 5 seconds>