D. Сломанный монитор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Иннокентия беда — cломался монитор компьютера. Теперь некоторые пиксели его монитора являются «битыми», то есть всегда имеют черный цвет. Как следствие, Иннокентий не может играть в обыкновенные компьютерные игры. В настоящий момент он играет в следующую игру со своим младшим братом Поликарпом.

Иннокентий вслепую пишет программу, которая на черном экране рисует квадратную белую рамку шириной в один пиксель. Так как монитор неисправен, то некоторые пиксели, которые должны быть белыми, остаются черными. Глядя на результат работы программы на экране, Поликарп должен угадать позицию и размер рамки Иннокентия. Поликарпу не очень нравится игра, но Иннокентий убедил брата играть, ведь «игра развивает фантазию и наблюдательность».

Помогите Поликарпу, автоматизировав его участие в игре. Напишите программу, которая находит такую возможную квадратную рамку, что:

  • ширина рамки составляет 1 пиксель,
  • рамка полностью помещается на экране,
  • все белые пиксели монитора расположены на рамке,
  • из всех рамок, которые удовлетворяют предыдущим трем условиям, искомая рамка должна иметь наименьший размер.

Формально, квадратная рамка представляет собой такие пиксели сплошного квадрата, которые находятся на краю квадрата, то есть не являются полностью окруженными другими пикселями квадрата. Например, если рамка имеет размер d = 3, то она состоит из 8 пикселей, если ее размер d = 2, то из 4, а если d = 1, то она вырождается в один пиксель.

Входные данные

В первой строке содержится разрешение монитора в виде пары целых чисел n, m (1 ≤ n, m ≤ 2000). Следующие n строк содержат ровно по m символов — состояние пикселей монитора на момент игры. Символ «.» (точка) соответствует черному пикселю, а символ «w» (строчная латинская буква w) — белому. Гарантируется, что хотя бы один пиксель монитора — белый.

Выходные данные

Выведите экран монитора, обозначив искомую рамку символами «+» (знак «плюс»). Те пиксели, которые во время игры были белыми, изменять не следует. Их следует выводить, используя «w». Если возможных вариантов размещения рамки минимального размера несколько, выведите любой из них.

Если искомой рамки не существует, то выведите вместо n строк единственную строку, содержащую число -1.

Примеры
Входные данные
4 8
..w..w..
........
........
..w..w..
Выходные данные
..w++w..
..+..+..
..+..+..
..w++w..
Входные данные
5 6
......
.w....
......
..w...
......
Выходные данные
......
+w+...
+.+...
++w...
......
Входные данные
2 4
....
.w..
Выходные данные
....
.w..
Входные данные
2 6
w..w.w
...w..
Выходные данные
-1
Примечание

В первом примере размер искомой рамки равен 4. Во втором примере размер искомой рамки равен 3. В третьем примере искомая рамка имеет размер 1. В четвертом примере искомой рамки не существует.