Igor has been into chess for a long time and now he is sick of the game by the ordinary rules. He is going to think of new rules of the game and become world famous.

Igor's chessboard is a square of size n × n cells. Igor decided that simple rules guarantee success, that's why his game will have only one type of pieces. Besides, all pieces in his game are of the same color. The possible moves of a piece are described by a set of shift vectors. The next passage contains a formal description of available moves.

Let the rows of the board be numbered from top to bottom and the columns be numbered from left to right from 1 to n. Let's assign to each square a pair of integers (x, y) — the number of the corresponding column and row. Each of the possible moves of the piece is defined by a pair of integers (dx, dy); using this move, the piece moves from the field (x, y) to the field (x + dx, y + dy). You can perform the move if the cell (x + dx, y + dy) is within the boundaries of the board and doesn't contain another piece. Pieces that stand on the cells other than (x, y) and (x + dx, y + dy) are not important when considering the possibility of making the given move (for example, like when a knight moves in usual chess).

Igor offers you to find out what moves his chess piece can make. He placed several pieces on the board and for each unoccupied square he told you whether it is attacked by any present piece (i.e. whether some of the pieces on the field can move to that cell). Restore a possible set of shift vectors of the piece, or else determine that Igor has made a mistake and such situation is impossible for any set of shift vectors.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 50).

The next n lines contain n characters each describing the position offered by Igor. The j-th character of the i-th string can have the following values: o — in this case the field (i, j) is occupied by a piece and the field may or may not be attacked by some other piece; x — in this case field (i, j) is attacked by some piece; . — in this case field (i, j) isn't attacked by any piece.

It is guaranteed that there is at least one piece on the board.


-----Output-----

If there is a valid set of moves, in the first line print a single word 'YES' (without the quotes). Next, print the description of the set of moves of a piece in the form of a (2n - 1) × (2n - 1) board, the center of the board has a piece and symbols 'x' mark cells that are attacked by it, in a format similar to the input. See examples of the output for a full understanding of the format. If there are several possible answers, print any of them.

If a valid set of moves does not exist, print a single word 'NO'.


-----Examples-----
Input
5
oxxxx
x...x
x...x
x...x
xxxxo

Output
YES
....x....
....x....
....x....
....x....
xxxxoxxxx
....x....
....x....
....x....
....x....

Input
6
.x.x..
x.x.x.
.xo..x
x..ox.
.x.x.x
..x.x.

Output
YES
...........
...........
...........
....x.x....
...x...x...
.....o.....
...x...x...
....x.x....
...........
...........
...........

Input
3
o.x
oxx
o.x

Output
NO



-----Note-----

In the first sample test the piece is a usual chess rook, and in the second sample test the piece is a usual chess knight.

Difficulty: interview

Starter code:

Solutions:
import sys
n = int(input())
s = [input() for i in range(n)]
a = [[1] * (2 * n) for i in range(2 * n)]

for i in range(n):
    for j in range(n):
        if s[i][j] != 'o':
            continue
        for x in range(n):
            for y in range(n):
                if s[x][y] == '.':
                    a[n + x - i][n + y - j] = 0
for i in range(n):
    for j in range(n):
        if s[i][j] != 'x':
            continue
        c = 0
        for x in range(n):
            for y in range(n):
                if s[x][y] == 'o' and a[n + i - x][n + j - y] == 1:
                    c = 1
                    break
            if c == 1:
                break
        if c == 0:
            print('NO')
            return
print('YES')
for i in range(1, 2 * n):
    for j in range(1, 2 * n):
        if i == n and j == n:
            print('o', end='')
        elif a[i][j] == 1:
            print('x', end='')
        else:
            print('.', end='')
    print('')



import sys
f = sys.stdin

n = int(f.readline().strip())
fig = []
place = []
for i in range(n):            
    place.append([-1]*(n)) 

for i in range(n):
    s = f.readline().strip()
    for k in range(len(s)):
        if s[k]=='o':
            fig.append((k, i))
            place[k][i] = -1
        elif s[k]=='x':
            place[k][i] = 1
        elif s[k]=='.': 
            place[k][i] = 0
hh = []
for i in range(2*n-1):            
    hh.append([1]*(2*n-1)) 

res = True
for fi in range(len(fig)):
    x = fig[fi][0] 
    y = fig[fi][1]
    for i in range(n):
        for k in range(n):
            r = place[k][i]
            if r==0:
                dx = k - x + n-1
                dy = i - y + n-1
                #print(x, y, k, i, dx, dy)
                hh[dx][dy] = 0

        
for i in range(n):
    for k in range(n):
        r = place[k][i]
        if r==1:
            beat = False
            for fi in range(len(fig)):
                dx = k - fig[fi][0] + n-1
                dy = i - fig[fi][1] + n-1
                
                if hh[dx][dy]!=0:
                    beat = True
            if not beat:
                res = False
hh[n-1][n-1] = -1
if res:                
    print('YES')
    for i in range(2*n-1):
        s = ''
        for k in range(2*n-1):
            if hh[k][i]==0:
                s += '.' 
            elif hh[k][i]==-1:
                s += 'o'
            else:
                s += 'x'
        print(s)
else:
    print('NO')

def main():
    n = int(input())
    d = [input() for i in range(n)]
    
    figures = []
    for i in range(n):
        for j in range(n):
            if d[i][j] == 'o':
                figures.append((i, j))
    
    result = [['x' for i in range(2 * n - 1)] for j in range(2 * n - 1)]
    result[n - 1][n - 1] = 'o'
    for i in range(n):
        for j in range(n):
            if d[i][j] == '.':
                for x, y in figures:
                    dx, dy = x - i, y - j
                    result[n - 1 - dx][n - 1 - dy] = '.'
    for i in range(n):
        for j in range(n):
            if d[i][j] == 'x':
                for x, y in figures:
                    dx, dy = x - i, y - j
                    if result[n - 1 - dx][n - 1 - dy] == 'x':
                        break
                else:
                    print("NO")
                    return
    print("YES")
    for i in result:
        print(''.join(i))
                        


main()


def main():
    n = int(input())
    d = [input() for i in range(n)]
    
    figures = []
    for i in range(n):
        for j in range(n):
            if d[i][j] == 'o':
                figures.append([i, j])
    
    result = [['x' for i in range(2 * n - 1)] for j in range(2 * n - 1)]
    result[n - 1][n - 1] = 'o'
    for i in range(n):
        for j in range(n):
            if d[i][j] == '.':
                for x, y in figures:
                    dx, dy = x - i, y - j
                    result[n - 1 - dx][n - 1 - dy] = '.'
    for i in range(n):
        for j in range(n):
            if d[i][j] == 'x':
                for x, y in figures:
                    dx, dy = x - i, y - j
                    if result[n - 1 - dx][n - 1 - dy] == 'x':
                        break
                else:
                    print("NO")
                    return
    print("YES")
    for i in result:
        print(''.join(i))
                        


main()



import datetime
import sys
import copy
import functools
import collections
import itertools

class Solution:
    def __init__(self):
        self.N = 0
        self.boards = None

    def test(self):
        pass

    def readInput(self):
        self.N = int(input())
        self.boards = []
        for i in range(self.N):
            self.boards.append(list(input()))

    def readMockInput(self):
        pass

    def solve(self):
        N = self.N
        impossibleMoves = set()
        chesses = list()
        notAttacked = list()
        # record all impossible moves
        for r in range(N):
            for c in range(N):
                if self.boards[r][c] == 'o':
                    chesses.append((r, c))
                elif self.boards[r][c] == '.':
                    notAttacked.append((r, c))
        # print(chesses)
        # print(notAttacked)
        for r, c in chesses:
            for i, j in notAttacked:
                impossibleMoves.add((i-r, j-c))
        # print(impossibleMoves)

        # check whether there are any conflicts
        # reboard = [['.' for c in range(N)] for r in range(N)]
        # for r, c in chesses:
        #     reboard[r][c] = 'o'

        startTime = datetime.datetime.now()

        for i in range(N):
            for j in range(N):
                if self.boards[i][j] == 'o':
                    continue
                for r, c in chesses:
                    if (i-r, j-c) not in impossibleMoves:
                        if self.boards[i][j] == '.':
                            print('NO')
                            return
                        self.boards[i][j] = 'v'


        # for r, c in chesses:
        #     for i in range(-N+1, N):
        #         for j in range(-N+1, N):
        #             # much faster than 2 for
        #             if (i, j) not in impossibleMoves:
        #                 nr = r + i
        #                 nc = c + j
        #                 if 0 <= nr < N and 0 <= nc < N and self.boards[nr][nc] != 'o':
        #                     # reboard[nr][nc] = 'x'
        #
        #                     if self.boards[nr][nc] == '.':
        #                         print('NO')
        #                         return
        #                     self.boards[nr][nc] = 'v'
        if sum([row.count('x') for row in self.boards]) > 0:
            print('NO')
            return
        # for r in range(N):
        #     for c in range(N):
        #         if self.boards[r][c] != reboard[r][c]:
        #             print('NO')
        #             return
        sys.stderr.write('Check Cost: {}\n'.format(datetime.datetime.now()-startTime))



        rn = 2*N-1
        res = [['.' for c in range(rn)] for r in range(rn)]
        res[N-1][N-1] = 'o'
        for i in range(-N+1, N):
            for j in range(-N+1, N):
                if not (i == 0 and j == 0) and (i, j) not in impossibleMoves:
                    res[i+N-1][j+N-1] = 'x'
        print('YES')
        for row in res:
            print(''.join(row))



solution = Solution()
solution.readInput()
startTime = datetime.datetime.now()
solution.solve()
sys.stderr.write('Time Cost:{}\n'.format(datetime.datetime.now() - startTime))

import sys
n = int(input())
s = [input() for i in range(n)]
a = [[1] * (2 * n) for i in range(2 * n)]

for i in range(n):
    for j in range(n):
        if s[i][j] != 'o':
            continue
        for x in range(n):
            for y in range(n):
                if s[x][y] == '.':
                    a[n + x - i][n + y - j] = 0
for i in range(n):
    for j in range(n):
        if s[i][j] != 'x':
            continue
        c = 0
        for x in range(n):
            for y in range(n):
                if s[x][y] == 'o' and a[n + i - x][n + j - y] == 1:
                    c = 1
                    break
            if c == 1:
                break
        if c == 0:
            print('NO')
            return
print('YES')
for i in range(1, 2 * n):
    for j in range(1, 2 * n):
        if i == n and j == n:
            print('o', end='')
        elif a[i][j] == 1:
            print('x', end='')
        else:
            print('.', end='')
    print('')

n = int(input())
b = [input() for i in range(n)]
h = [[False] * n for i in range(n)]
p = [[i, j] for i in range(n) for j in range(n) if b[i][j] == 'o']
v = [['.'] * (2 * n - 1) for i in range(2 * n - 1)]
def on(x, y):
    return x in range(n) and y in range(n)
def proc(dx, dy):
    for pi in p:
        if on(pi[0] + dx, pi[1] + dy) and b[pi[0] + dx][pi[1] + dy] == '.':
            return
    v[dx + n - 1][dy + n - 1] = 'x'
    for pi in p:
        if on(pi[0] + dx, pi[1] + dy):
            h[pi[0] + dx][pi[1] + dy] = True
for i in range(-(n - 1), n):
    for j in range(-(n - 1), n):
        proc(i, j)
if any(b[i][j] == 'x' and not h[i][j] for i in range(n) for j in range(n)):
    print('NO')
else:
    print('YES')
    v[n - 1][n - 1] = 'o'
    for vi in v:
        print(''.join(vi))


import math
from sys import stdin
from math import ceil
import sys

def __starting_point():
    n = int(input())
    table = list()
    # newT = list()
    for i in range(n):
        table.append(input())
    # for i in range(2 * n):
        # newT.append(1)
   # table = [input() for i in range(n)]
    newT = [[1] * (2 * n) for i in range(2 * n)]

    for i in range(n):
        for j in range(n):
            if table[i][j] != 'o':
                continue
            for a in range(n):
                for b in range(n):
                    if table[a][b] == '.':
                        newT[n + a - i][n + b - j] = 0
    for i in range(n):
        for j in range(n):
            if table[i][j] != 'x':
                continue
            piece = 0
            for a in range(n):
                for b in range(n):
                    if table[a][b] == 'o' and newT[n + i -a][n + j - b] == 1:
                        piece = 1
                        break
                if piece == 1:
                    break
            if piece == 0:
                print("NO")
                return
    print("YES")
    for i in range( 1, 2 * n):
        for j in range( 1, 2 * n):
            if i == n and j == n:
                print('o', end = '')
            elif newT[i][j] == 1:
                print('x', end = '')
            else:
                print('.', end = '')
        print('')



__starting_point()

import math
from sys import stdin
from math import ceil
import sys

def __starting_point():
    n = int(input())
    table = list()
    newT = list()
    for i in range(n):
        table.append(input())
    for i in range(2 * n):
         newT.append([1] * (2 * n))
    #table = [input() for i in range(n)]
    #newT = [[1] * (2 * n) for i in range(2 * n)]

    for i in range(n):
        for j in range(n):
            if table[i][j] != 'o':
                continue
            for a in range(n):
                for b in range(n):
                    if table[a][b] == '.':
                        newT[n  - i + a ][n  - j + b] = 0
    for i in range(n):
        for j in range(n):
            if table[i][j] != 'x':
                continue
            piece = 0
            for a in range(n):
                for b in range(n):
                    if table[a][b] == 'o' and newT[n + i -a][n + j - b] == 1:
                        piece = 1
                        break
                if piece == 1:
                    break
            if piece == 0:
                print("NO")
                return
    print("YES")
    for i in range( 1, 2 * n):
        for j in range( 1, 2 * n):
            if i == n and j == n:
                print('o', end = '')
            elif newT[i][j] == 1:
                print('x', end = '')
            else:
                print('.', end = '')
        print('')



__starting_point()

from sys import stdin

n = int(stdin.readline())

board = []

for x in range(n):
    board.append(list(stdin.readline().strip()))

moves = {y:{x:True for x in range(-n+1,n)} for y in range(-n+1,n)}

for x in range(n):
    for y in range(n):
        if board[x][y] == 'o':
            for a in range(n):
                for b in range(n):
                    if board[a][b] == '.':
                        moves[a-x][b-y] = False

recreate = [['.' for x in range(n)] for y in range(n)]

for x in range(n):
    for y in range(n):
        if board[x][y] == 'o':
            recreate[x][y] = 'o'
            for a in moves:
                for b in moves:
                    if moves[a][b]:
                        if 0 <= x+a < n and 0 <= y+b < n:
                            if recreate[x+a][y+b] != 'o':
                                recreate[x+a][y+b] = 'x'

if board == recreate:
    print('YES')

    for x in range(-n+1,n):
        l = []
        for y in range(-n+1,n):
            if moves[x][y]:
                l.append('x')
            else:
                l.append('.')
        if x == 0:
            l[n-1] = 'o'
        print(''.join(l))
else:
    print('NO')


import sys
fin = sys.stdin
n = int(fin.readline())
ma = [[None]] * n
for i in range(0, n):
    aux = fin.readline()
    aux = aux[:-1]
    ma[i] = list(aux)
r = []
for i in range(0, 2 * n - 1):
    r.append(None)
    r[i] = []
    for j in range(0, 2 * n - 1):
        r[i].append('x')
for i in range(0, n):
    for j in range(0, n):
        if ma[i][j] == 'o':
            for ii in range(0, n):
                for jj in range(0, n):
                    if ma[ii][jj] == '.':
                        r[n - 1 + ii - i][n - 1 + jj - j] = '.'
g = 1
r[n - 1][n - 1] = 'o'
for i in range(0, n):
    for j in range(0, n):
        if ma[i][j] == 'x':
            cg = 0
            for ii in range(0, n):
                for jj in range(0, n):
                    if ma[ii][jj] == 'o' and r[n - 1 - ii + i][n - 1 - jj + j] == 'x':
                        cg = 1
            if cg != 1:
                g = 0
if g != 1:
    print('NO')
else:
    print('YES')
    for line in r:
        print(''.join(line))