{"raw_statement":[{"iden":"statement","content":"Setsuna is playing a computer game called MITE (MogicianCraft Is Too Easy).\n\nIn this game, sugar cane is a valuable plant for crafting rockets and trading paper.\n\nSetsuna has a farm. To be a Farm Tycoon, she wants to plant some sugar cane on the land.\n\nThe 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$.\n\nThere are four types of blocks: sand block, sand block with sugar cane, rock block and water block.\n\nAt 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.\n\nTo plant sugar cane on a block, Setsuna should follow these rules:\n\nSetsuna wants to know how to maximize the number of blocks that sugar cane can be planted on.\n\nThe first line of the input contains two integers $n, m (1 <= n <= 30, 1 <= m <= 8)$.\n\nThe 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).\n\nPrint $n$ lines, each of which contains $m$ characters, where the $j$-th character of the $i$-th line is $c_{i , j}$. \n\n$c_{i , j}$ indicates the type of the block $(i, j)$ after reforming.\n\nIf the block $(i, j)$ is a water block, $c_{i , j}$ should be 'O'.\n\nIf the block $(i, j)$ is a sand block with sugar cane, $c_{i , j}$ should be 'X'.\n\nIf the block $(i, j)$ is just a sand block, $c_{i , j}$ should be '.'.\n\nIf the block $(i, j)$ is a rock block, $c_{i , j}$ should be '#'.\n\nYou should make sure the number of 'X' is maximal. If there are multiple solutions, print any.\n\nSolutions to sample $1$ and sample $2$ are shown below:\n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input3 3\n...\n.#.\n...\nOutputXOX\nX#X\nOXO\nInput3 3\n...\n#.#\n...\nOutputXOX\n#X#\nXOX\n"},{"iden":"note","content":"Solutions to sample $1$ and sample $2$ are shown below:  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 30 $, $ 1 \\leq m \\leq 8 $.  \nLet $ B = (b_{i,j})_{n \\times m} $ be the initial grid, where $ b_{i,j} \\in \\{ '.', \\# \\} $:  \n- $ b_{i,j} = '.' $: sand block,  \n- $ b_{i,j} = \\# $: rock block.  \n\nLet $ C = (c_{i,j})_{n \\times m} $ be the final grid, where $ c_{i,j} \\in \\{ '.', \\#, 'O', 'X' \\} $:  \n- $ c_{i,j} = \\# $: rock block (unchanged),  \n- $ c_{i,j} = '.' $: sand block (unmodified),  \n- $ c_{i,j} = 'O' $: water block (replaced from sand),  \n- $ c_{i,j} = 'X' $: sand block with sugar cane (planted).  \n\n**Constraints**  \n1. Rock blocks remain unchanged:  \n   $$\n   \\forall (i,j),\\ b_{i,j} = \\# \\Rightarrow c_{i,j} = \\#\n   $$  \n2. Only sand blocks can be replaced:  \n   $$\n   \\forall (i,j),\\ b_{i,j} = '.' \\Rightarrow c_{i,j} \\in \\{ '.', 'O', 'X' \\}\n   $$  \n3. Sugar cane ('X') can only be planted on sand blocks adjacent (up/down/left/right) to at least one water block ('O'):  \n   $$\n   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'\n   $$  \n   where $ \\mathcal{N}(i,j) = \\{ (i\\pm1,j), (i,j\\pm1) \\} \\cap \\{1,\\dots,n\\} \\times \\{1,\\dots,m\\} $.  \n4. Water blocks ('O') may be placed on any sand block, with no adjacency restriction.  \n\n**Objective**  \nMaximize the number of 'X' blocks:  \n$$\n\\max \\left| \\{ (i,j) \\mid c_{i,j} = 'X' \\} \\right|\n$$  \nsubject to the above constraints.  \nOutput any grid $ C $ achieving the maximum.","simple_statement":"Given an n×m grid with '.' (sand) and '#' (rock), you can turn any '.' into 'O' (water). Sugar cane ('X') can only be planted on '.' next to at least one 'O'. Maximize the number of 'X'. Output the grid with 'O', 'X', '.', '#' as specified.","has_page_source":false}