Problem B. Boulders

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

A pile of boulders is represented by a rectangular field of H rows with W columns each. Each element is either '.' (ASCII 46) representing empty space, 'o' representing a small boulder, or 'O' representing a large boulder.

A boulder is considered stable if at least one of the following is true:

A pile is stable if all boulders in it are stable.

Your program must remove minimal possible number of boulders from the pile so that the pile becomes stable.

Input file format

First line of input contains integers W H. Following H lines contain W characters each — pile representation.

Output file format

Output must contain H lines of W characters each — stable pile representation.

If there is more than one optimal solution, output any of them.

Constraints

1 ≤ W, H ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 2
O
o
.
o
2
6 5
....oO
...ooO
..oooO
.ooooO
oooooO
.....O
.....O
.....O
.....O
oooooO
3
3 3
O.o
.O.
o.O
...
...
o.O

0.105s 0.013s 13