终于有一天,亚瑟有足够的钱买一套公寓。他找到了一个靠近市中心且价格合理的绝佳选择。
亚瑟发现的公寓平面图看起来像一个由大小为 1 × 1 的正方形组成的 n × m 矩形。每个正方形都包含一面墙(此类正方形在平面图上用符号“*”表示)或自由空间(此类正方形在平面图上用符号“.”表示)。
公寓中的房间是由自由正方形组成的最大连通区域。如果正方形有公共边,则认为它们是相邻的。
亚瑟的老梦想是住在一套所有房间都是长方形的公寓里。他要求你计算为了实现这一目标需要拆除的最少墙壁数量。从正方形中移除墙壁后,它就变成了自由正方形。当拆除墙壁时,一些房间可能会合并成一个房间。
输入
输入的第一行包含两个整数 n, m (1 ≤ n, m ≤ 2000),表示 Arthur 公寓的大小。
接下来的 n 行每行包含 m 个符号——公寓的平面图。
如果单元格用符号“*”表示,则它包含一堵墙。
如果单元格用符号“.”表示那么这个牢房没有墙壁,而且这个牢房包含在一些房间里。
输出
输出 n 行,每行由 m 个符号组成,这些符号显示删除最小数量的墙壁以使每个房间(没有墙壁的最大连接区域)成为矩形后,亚瑟公寓平面图应是什么样子。
如果有多个可能的答案,则输出其中任何一个。
示例
输入 #1
5 5 .*.*. ***** .*.*. ***** .*.*.
输出 #1
.*.*. ***** .*.*. ***** .*.*.
输入 #2
6 7 ***.*.* ..*.*.* *.*.*.* *.*.*.* ..*...* *******
输出 #2
***...* ..*...* ..*...* ..*...* ..*...* *******
输入 #3
4 5 ..... ..... ..*** ..*..
输出 #3
..... ..... ..... .....