Innocentius has a problem — his computer monitor has broken. Now some of the pixels are "dead", that is, they are always black. As consequence, Innocentius can't play the usual computer games. He is recently playing the following game with his younger brother Polycarpus.

Innocentius is touch-typing a program that paints a white square one-pixel wide frame on the black screen. As the monitor is broken, some pixels that should be white remain black. Polycarpus should look at what the program displayed on the screen and guess the position and size of the frame Innocentius has painted. Polycarpus doesn't like the game but Innocentius persuaded brother to play as "the game is good for the imagination and attention".

Help Polycarpus, automatize his part in the gaming process. Write the code that finds such possible square frame that:  the frame's width is 1 pixel,  the frame doesn't go beyond the borders of the screen,  all white pixels of the monitor are located on the frame,  of all frames that satisfy the previous three conditions, the required frame must have the smallest size. 

Formally, a square frame is represented by such pixels of the solid square, that are on the square's border, that is, are not fully surrounded by the other pixels of the square. For example, if the frame's size is d = 3, then it consists of 8 pixels, if its size is d = 2, then it contains 4 pixels and if d = 1, then the frame is reduced to a single pixel.


-----Input-----

The first line contains the resolution of the monitor as a pair of integers n, m (1 ≤ n, m ≤ 2000). The next n lines contain exactly m characters each — the state of the monitor pixels at the moment of the game. Character "." (period, ASCII code 46) corresponds to the black pixel, and character "w" (lowercase English letter w) corresponds to the white pixel. It is guaranteed that at least one pixel of the monitor is white.


-----Output-----

Print the monitor screen. Represent the sought frame by characters "+" (the "plus" character). The pixels that has become white during the game mustn't be changed. Print them as "w". If there are multiple possible ways to position the frame of the minimum size, print any of them.

If the required frame doesn't exist, then print a single line containing number -1.


-----Examples-----
Input
4 8
..w..w..
........
........
..w..w..

Output
..w++w..
..+..+..
..+..+..
..w++w..

Input
5 6
......
.w....
......
..w...
......

Output
......
+w+...
+.+...
++w...
......

Input
2 4
....
.w..

Output
....
.w..

Input
2 6
w..w.w
...w..

Output
-1



-----Note-----

In the first sample the required size of the optimal frame equals 4. In the second sample the size of the optimal frame equals 3. In the third sample, the size of the optimal frame is 1. In the fourth sample, the required frame doesn't exist.

Difficulty: HARD
Tags: Greedy algorithms

Complete search

Implementation

Constructive algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
from itertools import chain

def draw_square(scr, square_a, ymin, xmin):
	for i in range(square_a + 1):
		if scr[ymin][xmin + i] != 'w':
			scr[ymin] = scr[ymin][:xmin + i] + '+' + scr[ymin][xmin + i + 1:]
		if scr[ymin + square_a][xmin + i] != 'w':
			scr[ymin + square_a] = scr[ymin + square_a][:xmin + i] + '+' + scr[ymin + square_a][xmin + i + 1:]
		if scr[ymin + i][xmin] != 'w':
			scr[ymin + i] = scr[ymin + i][:xmin] + '+' + scr[ymin + i][xmin + 1:]
		if scr[ymin + i][xmin + square_a] != 'w':
			scr[ymin + i] = scr[ymin + i][:xmin + square_a] + '+' + scr[ymin + i][xmin + square_a + 1:]
	return scr

def find_a(pixel, y, x):
	ymax = xmax = 0
	ymin = y
	xmin = x
	ymaxl = []
	yminl = []
	xmaxl = []
	xminl = []
	count_pixel = len(pixel) // 2
	for i in range(count_pixel):
		if ymax < pixel[2 * i]:
			ymax = pixel[2 * i]
		if ymin > pixel[2 * i]:
			ymin = pixel[2 * i]
		if xmax < pixel[2 * i + 1]:
			xmax = pixel[2 * i + 1]
		if xmin > pixel[2 * i + 1]:
			xmin = pixel[2 * i + 1]
	for i in range(count_pixel):
		f = True
		if pixel[2 * i] == ymax:
			f = False
			ymaxl.append(pixel[2 * i])
			ymaxl.append(pixel[2 * i + 1])
		if pixel[2 * i] == ymin:
			f = False
			yminl.append(pixel[2 * i])
			yminl.append(pixel[2 * i + 1])
		if pixel[2 * i + 1] == xmax:
			f = False
			xmaxl.append(pixel[2 * i])
			xmaxl.append(pixel[2 * i + 1])
		if pixel[2 * i + 1] == xmin:
			f = False
			xminl.append(pixel[2 * i])
			xminl.append(pixel[2 * i + 1])
		if f:
			print('-1')
			return
	return (ymax, ymin, xmax, xmin, ymaxl, yminl, xmaxl, xminl)

def main():
	(y, x) = list(map(int, input().split()))
	scr = []
	for i in range(y):
		scr.append(input())
	pixel = []
	for i in range(y):
		for j in range(x):
			if scr[i][j] == 'w':
				pixel.append(i)
				pixel.append(j)
	(ymax, ymin, xmax, xmin, ymaxl, yminl, xmaxl, xminl) = find_a(pixel, y, x)
	count_ymax = len(ymaxl) / 2
	count_ymin = len(yminl) / 2
	count_xmax = len(xmaxl) / 2
	count_xmin = len(xminl) / 2
	countx_ymax = ymaxl[1::2].count(xmax) + ymaxl[1::2].count(xmin)
	countx_ymin = yminl[1::2].count(xmax) + yminl[1::2].count(xmin)
	county_xmax = xmaxl[::2].count(ymax) + xmaxl[::2].count(ymin)
	county_xmin = xminl[::2].count(ymax) + xminl[::2].count(ymin)
	if ymax - ymin > xmax - xmin:
		square_a = ymax - ymin
		if county_xmax < count_xmax and county_xmin < count_xmin:
			if xmax == xmin:
				if xmin + square_a < x:
					xmax = xmin + square_a
				elif xmax - square_a >= 0:
					xmin = xmax - square_a
				else:
					print('-1')
					return
			else:
				print('-1')
				return
		elif county_xmax < count_xmax and county_xmin == count_xmin:
			xmin = xmax - square_a
			if xmin < 0:
				print('-1')
				return
		elif county_xmax == count_xmax and county_xmin < count_xmin:
			xmax = xmin + square_a
			if xmax >= x:
				print('-1')
				return
		elif county_xmax == count_xmax and county_xmin == count_xmin:
			if square_a < x:
				if xmin + square_a < x:
					xmax = xmin + square_a
				elif xmax - square_a >= 0:
					xmin = xmax - square_a
				else:
					xmin = 0
					xmax = xmin + square_a
			else:
				print('-1')
				return
	elif ymax - ymin < xmax - xmin:
		square_a = xmax - xmin
		if countx_ymax < count_ymax and countx_ymin < count_ymin:
			if ymax == ymin:
				if ymin + square_a < y:
					ymax = ymin + square_a
				elif ymax - square_a >= 0:
					ymin = ymax - square_a
				else:
					print('-1')
					return
			else:
				print('-1')
				return
		elif countx_ymax < count_ymax and countx_ymin == count_ymin:
			ymin = ymax - square_a
			if ymin < 0:
				print('-1')
				return
		elif countx_ymax == count_ymax and countx_ymin < count_ymin:
			ymax = ymin + square_a
			if ymax >= y:
				print('-1')
				return
		elif countx_ymax == count_ymax and countx_ymin == count_ymin:
			if square_a < y:
				if ymin + square_a < y:
					ymax = ymin + square_a
				elif ymax - square_a >= 0:
					ymin = ymax - square_a
				else:
					ymin = 0
					ymax = ymin + square_a
			else:
				print('-1')
				return
	elif ymax - ymin == xmax - xmin:
		square_a = xmax - xmin
	scr = draw_square(scr, square_a, ymin, xmin)
	for i in range(y):
		print(scr[i])

def __starting_point():
	main()
__starting_point()


def readln():
	return list(map(int, input().split()))
import sys

def exit():
	print(-1)
	sys.exit()
(n, m) = readln()
mon = [list(input()) for _ in range(n)]
hor = [i for i in range(n) if mon[i] != ['.'] * m]
rmon = list(zip(*mon))
ver = [j for j in range(m) if rmon[j] != ('.',) * n]
mini = hor[0]
maxi = hor[-1]
minj = ver[0]
maxj = ver[-1]
cnt_in = len([1 for i in range(mini + 1, maxi) for j in range(minj + 1, maxj) if mon[i][j] == 'w'])
cnt_l = len([1 for i in range(mini + 1, maxi) if mon[i][minj] == 'w'])
cnt_r = len([1 for i in range(mini + 1, maxi) if mon[i][maxj] == 'w'])
cnt_d = len([1 for j in range(minj + 1, maxj) if mon[mini][j] == 'w'])
cnt_u = len([1 for j in range(minj + 1, maxj) if mon[maxi][j] == 'w'])
if cnt_in:
	exit()
if maxi - mini < maxj - minj:
	k = maxj - minj + 1
	if maxi == mini and cnt_d:
		if mini >= k - 1:
			mini -= k - 1
		elif maxi + k - 1 < n:
			maxi += k - 1
		else:
			exit()
	else:
		if not cnt_d:
			mini = max(0, maxi - k + 1)
		if maxi - maxi + 1 != k and (not cnt_u):
			maxi = min(mini + k - 1, n - 1)
		if maxi - mini + 1 != k:
			exit()
else:
	k = maxi - mini + 1
	if maxj == minj and cnt_l:
		if minj >= k - 1:
			minj -= k - 1
		elif maxj + k - 1 < m:
			maxj += k - 1
		else:
			exit()
	else:
		if not cnt_l:
			minj = max(0, maxj - k + 1)
		if maxj - minj + 1 != k and (not cnt_r):
			maxj = min(minj + k - 1, m - 1)
		if maxj - minj + 1 != k:
			exit()
for i in range(mini, maxi + 1):
	if mon[i][minj] == '.':
		mon[i][minj] = '+'
for i in range(mini, maxi + 1):
	if mon[i][maxj] == '.':
		mon[i][maxj] = '+'
for j in range(minj, maxj + 1):
	if mon[mini][j] == '.':
		mon[mini][j] = '+'
for j in range(minj, maxj + 1):
	if mon[maxi][j] == '.':
		mon[maxi][j] = '+'
print('\n'.join([''.join(row) for row in mon]))