Innocentius 有一个问题 — 他的电脑显示器坏了。现在有些像素“死了”,即它们始终是黑色的。因此,Innocentius 无法玩通常的电脑游戏。他最近正在和他的弟弟波利卡波斯玩以下游戏。
Innocentius 正在触摸打字一个程序,该程序会在黑色屏幕上绘制一个白色方形单像素宽框。由于显示器损坏,一些本应是白色的像素仍然是黑色的。波利卡普斯应该看看程序在屏幕上显示的内容,并猜测英诺森提乌斯绘制的框架的位置和大小。波利卡普斯不喜欢这个游戏,但英诺森提乌斯说服哥哥玩,因为“这个游戏有利于想象力和注意力”。
帮助Polycarpus,使他在游戏过程中的部分自动化。编写代码来找到这样的可能的方框:
- 框架的宽度为 1 像素,
- 框架不超出屏幕边界,
- 显示器的所有白色像素都位于框架上,
- 在满足前面三个条件的所有帧中,所需的帧必须具有最小的尺寸。
形式上,正方形框架由实心正方形的像素表示,这些像素位于正方形的边界上,即不完全被正方形的其他像素包围。例如,如果帧的大小为 d = 3,则它由 8 个像素组成,如果其大小为 d = 2,则它包含 4 个像素,如果 d = 1,则该帧缩小为单个像素。
输入
第一行包含显示器的分辨率,作为一对整数 n, m (1 ≤ n, m ≤ 2000)。接下来的 n 行每行恰好包含 m 个字符——游戏时显示器像素的状态。特点 ”。” (句号,ASCII码46)对应黑色像素,字符“w”(小写英文字母w)对应白色像素。保证显示器至少有一个像素是白色的。
输出
打印监视器屏幕。用字符“+”(“加号”字符)表示所查找的帧。游戏过程中变白的像素不得更改。将它们打印为“w”。如果有多种可能的方法来定位最小尺寸的框架,请打印其中任何一种。
如果所需的帧不存在,则打印包含数字 -1 的单行。
示例
输入 #1
4 8 ..w..w.. ........ ........ ..w..w..
输出 #1
..w++w.. ..+..+.. ..+..+.. ..w++w..
输入 #2
5 6 ...... .w.... ...... ..w... ......
输出 #2
...... +w+... +.+... ++w... ......
输入 #3
2 4 .... .w..
输出 #3
.... .w..
输入#4
2 6 w..w.w ...w..
输出#4
-1
注意
在第一个样本中,所需的最佳帧大小等于 4。在第二个样本中,最佳帧的大小等于 3。在第三个样本中,最佳帧的大小为 1。在第四个样本中,所需的帧不存在。