Steve is a professional miner who is trying to mine copper ores! Steve is currently in a mine which can be represented as an $$$N \times N$$$ grid. Each cell in the grid is identified by a pair $$$(R, C)$$$, meaning that the cell is in the $$$R$$$-th row from top to bottom and the $$$C$$$-th column from left to right. Two cells are said to be adjacent if they share a common edge (in the direction of up, down, left, or right). Formally, $$$(R, C)$$$ is adjacent to $$$(R-1, C)$$$, $$$(R+1, C)$$$, $$$(R, C-1)$$$, and $$$(R, C+1)$$$, if any exist. In the mine, there are exactly $$$3$$$ copper cells, and all the remaining cells are stone cells.
Steve is trying to mine a mine shaft to connect all $$$3$$$ copper cells by mining some (possibly, zero or all) stone cells only. The copper cells are said to be connected if there exists a path of adjacent cells consisting of copper cells and mined cells between any two copper cells.
Please help Steve find a way to connect all $$$3$$$ copper cells by mining the minimum number of stone cells. If there are multiple ways to achieve this minimum, any of them is accepted.
The first line contains one integer $$$N$$$ $$$(2 \leq N \leq 500)$$$, representing the size of the mine.
The following $$$N$$$ lines each contain a string of $$$N$$$ characters, describing a row of the mine. The $$$j$$$-th character on the $$$i$$$-th line represents the cell at $$$(i, j)$$$. Each character is either X or . if the cell at $$$(i, j)$$$ is a copper cell or a stone cell, respectively.
It is guaranteed that there are exactly $$$3$$$ copper cells (X) in the mine.
The output should consist of $$$N$$$ lines, each containing a string of $$$N$$$ characters, describing the mine after mining the mine shaft. The $$$j$$$-th character on the $$$i$$$-th line represents the cell at $$$(i, j)$$$. Each character is either X, ., or * if the cell at $$$(i, j)$$$ is a copper cell, a stone cell, or a mined cell, respectively.
After mining, the copper cells must remain at the same locations, but you can change some stone cells to mined cells.
If there are multiple ways to achieve the minimum number of stone cells mined, any of them is accepted.
5...X.........X..X........
...X. ...*. ...X. .X**. .....
5......X.X........X.......
..... .X*X. ..*.. ..X.. .....
2XXX.
XX X.
For the first sample test, the copper cells are located at $$$(1, 4)$$$, $$$(3, 4)$$$, and $$$(4, 2)$$$, and the stone cells at $$$(2, 4)$$$, $$$(4, 3)$$$ and $$$(4, 4)$$$ are mined. It can be proven that the minimum number of stone cells needed to be mined to connect the copper cells is $$$3$$$.
The following diagram shows the mine before and after mining.
Note that there are other answers, e.g.
...X.
...*.
.**X.
.X...
.....
Image source: Minecraft
