## Problem B. Boulders ≡

• problems
 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:

• it is located at the last row;
• it is located directly above a large boulder;
• there are boulders of any kind both to the right and to the left of it.
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.

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.068s 0.009s 13