406954: GYM102623 M MITE

Setsuna is playing a computer game called MITE (MogicianCraft Is Too Easy).

In this game, sugar cane is a valuable plant for crafting rockets and trading paper.

Setsuna has a farm. To be a Farm Tycoon, she wants to plant some sugar cane on the land.

The farm can be seen as a two-dimensional plane composed of $$$n \times m$$$ blocks, and the size of each block is exactly $$$1 \times 1$$$.

There are four types of blocks: sand block, sand block with sugar cane, rock block and water block.

At the beginning, there are only sand blocks and rock blocks. But, Setsuna can replace sand blocks with water blocks, and she can do this any number of times.

To plant sugar cane on a block, Setsuna should follow these rules:

1. Sugar cane can only be planted on sand blocks on the farm.
2. The sand block sugar cane planted on must be adjacent to at least one water block. Two blocks are considered adjacent if and only if they share an edge.

Setsuna wants to know how to maximize the number of blocks that sugar cane can be planted on.

The first line of the input contains two integers $$$n,m(1 \leq n \leq 30,1 \leq m \leq 8)$$$.

The next $$$n$$$ lines contains $$$m$$$ characters each, where the $$$j$$$-th character of the $$$i$$$-th line is $$$b_{i,j}$$$ ($$$b_{i,j}$$$ is either '.' if the block $$$(i,j)$$$ is a sand block or '#' if the block $$$(i,j)$$$ is a rock block).

Print $$$n$$$ lines, each of which contains $$$m$$$ characters, where the $$$j$$$-th character of the $$$i$$$-th line is $$$c_{i,j}$$$.

$$$c_{i,j}$$$ indicates the type of the block $$$(i,j)$$$ after reforming.

If the block $$$(i,j)$$$ is a water block, $$$c_{i,j}$$$ should be 'O'.

If the block $$$(i,j)$$$ is a sand block with sugar cane, $$$c_{i,j}$$$ should be 'X'.

If the block $$$(i,j)$$$ is just a sand block, $$$c_{i,j}$$$ should be '.'.

If the block $$$(i,j)$$$ is a rock block, $$$c_{i,j}$$$ should be '#'.

You should make sure the number of 'X' is maximal. If there are multiple solutions, print any.

3 3
...
.#.
...

XOX
X#X
OXO

3 3
...
#.#
...

XOX
#X#
XOX

Solutions to sample $$$1$$$ and sample $$$2$$$ are shown below: