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: interview

Starter code:

Solutions:
3

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

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:
    return
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:
            return
    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:
            return
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:
            return
    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:
            return
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]))


from itertools import chain
# To draw square: if point isn't 'w', draw '+'
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
# To find the side length of a square, and if there is some point beside the edge of a square it'll print '-1'
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 some point beside the edge of a square: like the 'x'
        # 5 7
        # .......
        # .+++...
        # .+x+...
        # .www...
        # .......
        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 = []
    # To collect the point info
    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)
    #print('ymax:%d,ymin:%d,xmax:%d,xmin:%d'%(ymax,ymin,xmax,xmin))
    #print(f'ymaxl:\n{ymaxl}\nyminl:\n{yminl}\nxmaxl:\n{xmaxl}\nxminl:\n{xminl}\ncounty_xmax:{county_xmax}\ncounty_xmin:{county_xmin}\ncountx_ymax:{countx_ymax}\ncountx_ymin:{countx_ymin}')
    # There are three conditions:
    # 1.height > width  2.height < width    3.height == width
    # eg: 1.height > width:
    # so square_a = height
    if ymax - ymin > xmax - xmin:
        square_a = ymax - ymin
        # if the point form a rectangle:
        # 5 7
        # .......
        # .ww....
        # .wx....
        # .ww....
        # .......
        # or
        # 5 7
        # .......
        # .w.....
        # .w.....
        # .w.....
        # .......
        if county_xmax < count_xmax and county_xmin < count_xmin:
            # 5 7
            # .......
            # .w++...
            # .w.+...
            # .w++...
            # .......
            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
        # if the point from the shape of [ like:
        # 5 7
        # .......
        # .www...
        # .w.....
        # .www...
        # .......
        elif county_xmax < count_xmax and county_xmin == count_xmin:
            xmin = xmax - square_a
            if xmin < 0:
                print('-1')
                return
        # if the point from the shape of ] like:
        # 5 7
        # .......
        # .www...
        # ...w...
        # .www...
        # .......
        elif county_xmax == count_xmax and county_xmin < count_xmin:
            xmax = xmin + square_a
            if xmax >= x:
                print('-1')
                return
        # if there is some point to make county_xmax == count_xmax and county_xmin == count_xmin like:
        # 5 7
        # .......
        # .w.....
        # .......
        # ..w....
        # .......
        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
                # sp:
                # 5 5
                # .w...
                # .....
                # .....
                # .....
                # ..w..
                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
    #print('ymax:%d,ymin:%d,xmax:%d,xmin:%d,a:%d'%(ymax,ymin,xmax,xmin,square_a))
    scr = draw_square(scr, square_a, ymin, xmin)
    for i in range(y):
        print(scr[i])
def __starting_point():
    main()
    #while True:
    #    main()

__starting_point()