RPG Maker

You are drawing the map of an RPG. The map is a grid with $H$ rows and $W$ columns, and every cell holds one of four symbols.

• @: the start cell. The story begins here.
• *: a city cell. The story passes through this cell or ends at it.
• #: a road cell.
• .: an empty cell.

The start cell and every city cell are already placed under the restrictions given in the input section, and no road cell is placed yet. You decide which empty cells become road cells.

The map must hold one journey. The story must not branch, so the journey must not fork either. A journey is a sequence of cells that satisfies all of the following conditions.

1. The journey holds as many city cells as possible.
2. The journey consists of distinct cells that are not empty.
3. The journey begins at the start cell.
4. The journey ends at a city cell.
5. Every road cell belongs to the journey. No road cell lies outside the journey.
6. Every cell of the journey other than the first and the last shares an edge with exactly two cells of the journey. The first cell and the last cell each share an edge with exactly one cell of the journey.
7. The order in which the cities are visited does not matter.

You may turn any number of empty cells into road cells. Print the finished map.

The input is a single test case in the following form.

H W
S1
S2
...
SH

The first line holds two integers $H$ and $W$. There are positive integers $n$ and $m$ with $H = 4n - 1$ and $W = 4m - 1$, and $1 \le n, m \le 10$. The next $H$ lines are the map without road cells. Line $i+1$ is a string $S_i$ of length $W$. The $j$-th character of $S_i$ is *, @ or . when $i$ and $j$ are both odd, and . otherwise. The grid holds exactly one @ and at least one city cell.

Several maps can satisfy the conditions, so only the map produced by the construction below is accepted.

Number the rows $1$ to $H$ from the top and the columns $1$ to $W$ from the left. Call a cell whose row number and column number are both odd a vertex, and write vertex $(i, j)$ for the cell in row $2i+1$ and column $2j+1$, where $0 \le i < 2n$ and $0 \le j < 2m$. Two vertices whose coordinates differ by $1$ in exactly one place are neighbors, and the single cell between them is the cell that joins them.

Write down a cycle $C$ that visits each of the $4nm$ vertices once, in this order.

1. $(0, 0), (0, 1), \ldots, (0, 2m-1)$
2. Then, for $i = 1$ up to $i = 2n-1$ in order, write $(i, 2m-1), (i, 2m-2), \ldots, (i, 1)$ when $i$ is odd, and $(i, 1), (i, 2), \ldots, (i, 2m-1)$ when $i$ is even.
3. Then $(2n-1, 0)$
4. Then $(2n-2, 0), (2n-3, 0), \ldots, (1, 0)$

Two vertices written next to each other in $C$ are neighbors, and the last vertex $(1, 0)$ is a neighbor of the first vertex $(0, 0)$.

Start at the vertex that holds @ and move along the order written in $C$. On reaching the end of $C$, continue from its beginning, and stop once all $4nm$ vertices have been listed once. Cut the resulting list right after its last city vertex. The journey is the remaining vertices together with the joining cell of each pair of vertices that are next to each other in the list.

Print the map on $H$ lines. Turn every cell of the journey that was empty in the input into #, and leave every other cell as it is in the input. The journey built this way passes through every city cell.