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:
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 <= n <= 30, 1 <= m <= 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.
Solutions to sample $1$ and sample $2$ are shown below:
## Input
The first line of the input contains two integers $n, m (1 <= n <= 30, 1 <= m <= 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).
## Output
Print $n$ lines, each of which contains $m$ characters, where the $j$-th character of the $i$-th line is $c_(i comma j)$. $c_(i comma j)$ indicates the type of the block $(i, j)$ after reforming.If the block $(i, j)$ is a water block, $c_(i comma j)$ should be 'O'.If the block $(i, j)$ is a sand block with sugar cane, $c_(i comma j)$ should be 'X'.If the block $(i, j)$ is just a sand block, $c_(i comma j)$ should be '.'.If the block $(i, j)$ is a rock block, $c_(i comma j)$ should be '#'.You should make sure the number of 'X' is maximal. If there are multiple solutions, print any.
[samples]
## Note
Solutions to sample $1$ and sample $2$ are shown below:
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 30 $, $ 1 \leq m \leq 8 $.
Let $ B = (b_{i,j})_{n \times m} $ be the initial grid, where $ b_{i,j} \in \{ '.', \# \} $:
- $ b_{i,j} = '.' $: sand block,
- $ b_{i,j} = \# $: rock block.
Let $ C = (c_{i,j})_{n \times m} $ be the final grid, where $ c_{i,j} \in \{ '.', \#, 'O', 'X' \} $:
- $ c_{i,j} = \# $: rock block (unchanged),
- $ c_{i,j} = '.' $: sand block (unmodified),
- $ c_{i,j} = 'O' $: water block (replaced from sand),
- $ c_{i,j} = 'X' $: sand block with sugar cane (planted).
**Constraints**
1. Rock blocks remain unchanged:
$$
\forall (i,j),\ b_{i,j} = \# \Rightarrow c_{i,j} = \#
$$
2. Only sand blocks can be replaced:
$$
\forall (i,j),\ b_{i,j} = '.' \Rightarrow c_{i,j} \in \{ '.', 'O', 'X' \}
$$
3. Sugar cane ('X') can only be planted on sand blocks adjacent (up/down/left/right) to at least one water block ('O'):
$$
c_{i,j} = 'X' \Rightarrow b_{i,j} = '.' \quad \text{and} \quad \exists (i',j') \in \mathcal{N}(i,j) \text{ s.t. } c_{i',j'} = 'O'
$$
where $ \mathcal{N}(i,j) = \{ (i\pm1,j), (i,j\pm1) \} \cap \{1,\dots,n\} \times \{1,\dots,m\} $.
4. Water blocks ('O') may be placed on any sand block, with no adjacency restriction.
**Objective**
Maximize the number of 'X' blocks:
$$
\max \left| \{ (i,j) \mid c_{i,j} = 'X' \} \right|
$$
subject to the above constraints.
Output any grid $ C $ achieving the maximum.