Problem B. Boulders

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

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.023s 0.008s 9