题目描述

在 Berland 附近有一座名为 Berodoskar 的石质小岛。国王决定在岛上利用天然火山口建造淡水蓄水池，并通过水管与海洋相连。

小岛被表示为一个 $N\times M$ 的矩形网格。每个格子为：

• X：该格子属于某个火山口；
• .：普通地面，可以铺设水管。

如果两个 X 格子有公共边，则它们属于同一个火山口。题目保证没有 X 格子直接与岛外海洋相邻，也就是说边界格子不会是 X。矩形外部全部视为海洋。

你需要在若干个 . 格子中铺设水管。每一段水管恰好占据一个完整的普通格子，输出时将该格子改成 *。两个水管格子有公共边时可以互相连通；如果某个水管格子与火山口的 X 格子有公共边，则这条水管与该火山口连通；如果水管到达网格边界，则它与海洋连通。

要求至少有 两个不同的火山口 能够通过铺设的水管与海洋连通。允许连接两个以上的火山口，也允许使用两条互不连通的独立水管。

请使铺设水管所占用的格子数最少，并输出任意一种最优方案。

注意：不能把一个火山口本身当作水管的一部分，也不能通过穿过另一个火山口来连接海洋。

输入格式

第一行包含两个整数 $N,M$，表示网格的行数和列数。

接下来 $N$ 行，每行恰好包含 $M$ 个字符 X 或 .，表示小岛地图。

数据范围：

• $3\le N,M\le15$；
• 所有边界格子均不是 X；
• 至少存在两个能够通过普通地面到达海洋的火山口。

输出格式

输出 $N$ 行，每行 $M$ 个字符。

输出地图与输入地图格式相同，但所有铺设水管的 . 格子改为 *。原有的 X 格子必须保持不变。

如果存在多种使用最少格子数的方案，输出任意一种即可。

样例 1

5 7
.......
.......
..X....
.....X.
.......

一种合法最优输出为：

.......
.......
**X....
.....X*
.......

样例 2

10 13
.............
.............
..XXXXX......
..X..X.......
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............

一种合法最优输出为：

........*....
........*....
..XXXXX**....
..X..X..*....
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............