题目描述

Lesya 是一名景观设计师。她的任务是在公园中用尽可能少的建筑材料，围绕湖修建一条道路。道路只能修建在草坪格子上。

公园是一张 $h\times w$ 的网格，每个格子可能是陆地、草坪或湖泊。输入给出草坪格子的位置。保证：

1. 草坪格子集合是 4-连通的，即任意两个草坪格子之间可以通过共边相邻的草坪格子互相到达；
2. 非草坪格子中恰好有一个内部 4-连通区域，它就是湖；
3. 可以从某个草坪格子出发，沿草坪绕湖一圈并回到起点，使湖位于这个闭合路线内部。称这样的格子集合为“4-环绕湖”。

Lesya 需要把一些草坪格子改造成道路格子，使道路 4-环绕湖，并使道路格子数最少。

请输出任意一种最优道路方案。

输入格式

第一行包含两个整数 $h,w$：

接下来 $h$ 行，每行包含 $w$ 个字符 . 或 #。其中 # 表示草坪，. 表示陆地或湖泊。

保证草坪 4-连通，且非草坪格子中恰好有一个内部 4-连通区域。

输出格式

输出 $h$ 行，每行 $w$ 个字符，表示最优道路方案。

• # 表示道路格子；
• . 表示其他格子。

注意，道路只能建在原来的草坪格子上。

如果有多种最优方案，输出任意一种。

样例

4 6
######
#.#.##
#...#.
#####.

#####.
#...#.
#...#.
#####.