问题描述

你计划创建一张 RPG 游戏的地图。这张地图由一个 $H \times W$ 的网格表示。这个网格的每个单元格可以是 @、*、# 或 . 四种符号之一。这些符号的含义如下：

• @：起始单元格。故事应该从这个单元格开始。
• *：城市单元格。故事经过或以这个单元格结束。
• #：道路单元格。
• .：空单元格。

在某些约束条件下，你已经确定了起始单元格和所有城市单元格的位置，但还没有确定道路单元格的位置。现在，你需要决定哪些单元格应该被设置为道路单元格。

在这里，你希望地图上存在一条"旅程"。由于你希望消除故事的分支，旅程必须是不分叉的。更具体地说，旅程是一个单元格序列，必须满足以下条件：

1. 旅程中应包含尽可能多的城市单元格。
2. 旅程必须由此地图中不同的非空单元格组成。
3. 旅程必须以起始单元格开始。
4. 旅程必须以城市单元格之一结束。
5. 旅程必须包含所有道路单元格。也就是说，旅程中没有包含的道路单元格不应存在。
6. 旅程必须是不分叉的。更具体地说，除了旅程结束的单元格外，所有道路单元格和城市单元格必须与另外两个也包含在旅程中的单元格共享边界。此外，起始单元格和旅程结束的单元格必须与旅程中的另一个单元格共享边界。
7. 你不需要考虑在旅程中访问城市的顺序。

初始地图中不包含任何道路单元格。你可以将任何空单元格更改为道路单元格，以满足上述条件。你的任务是打印一张地图，使得旅程中的城市数量最大化。

输入

输入包含以下格式的单个测试用例。

$H$ $W$ $S\_1$ $S\_2$ $\\vdots$ $S\_H$

第一行由两个整数 $H$ 和 $W$ 组成。保证 $H = 4n - 1$ 且 $W = 4m - 1$，其中 $n$ 和 $m$ 是正整数 ($1 \le n, m \le 10$)。接下来的 $H$ 行表示一个没有道路单元格的地图。第 $i+1$ 行由长度为 $W$ 的字符串 $S\_i$ 组成。如果 $i$ 和 $j$ 都是奇数，则 $S\_i$ 的第 $j$ 个字符可以是 *、@ 或 .；否则只能是 .。网格中 @ 出现的次数恰好为一次。保证网格上有一个或多个城市单元格。

输出

打印一个指示旅程的地图。如果有多个地图满足条件，则可以打印任何一个。

示例输入 1

11 7
.......
.......
*.....*
.......
..@....
.......
*......
.......
....*..
.......
.......

示例输出 1

.......
.......
*#####*
......#
..@...#
..#.###
*##.#..
#...#..
####*..
.......
.......

示例输入 2

7 11
........*..
...........
...........
...........
....*...*..
...........
..*.@...*..

示例输出 2

........*..
........#..
........#..
........#..
..##*##.*..
..#...#.#..
..*#@.##*..