The zombies are gathering in their secret lair! Heidi will strike hard to destroy them once and for all. But there is a little problem... Before she can strike, she needs to know where the lair is. And the intel she has is not very good.

Heidi knows that the lair can be represented as a rectangle on a lattice, with sides parallel to the axes. Each vertex of the polygon occupies an integer point on the lattice. For each cell of the lattice, Heidi can check the level of Zombie Contamination. This level is an integer between 0 and 4, equal to the number of corners of the cell that are inside or on the border of the rectangle.

As a test, Heidi wants to check that her Zombie Contamination level checker works. Given the output of the checker, Heidi wants to know whether it could have been produced by a single non-zero area rectangular-shaped lair (with axis-parallel sides). [Image]


-----Input-----

The first line of each test case contains one integer N, the size of the lattice grid (5 ≤ N ≤ 50). The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice. Every character of every line is a digit between 0 and 4.

Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate. This means that the first row corresponds to cells with coordinates (1, N), ..., (N, N) and the last row corresponds to cells with coordinates (1, 1), ..., (N, 1).


-----Output-----

The first line of the output should contain Yes if there exists a single non-zero area rectangular lair with corners on the grid for which checking the levels of Zombie Contamination gives the results given in the input, and No otherwise.


-----Example-----
Input
6
000000
000000
012100
024200
012100
000000

Output
Yes



-----Note-----

The lair, if it exists, has to be rectangular (that is, have corners at some grid points with coordinates (x_1, y_1), (x_1, y_2), (x_2, y_1), (x_2, y_2)), has a non-zero area and be contained inside of the grid (that is, 0 ≤ x_1 < x_2 ≤ N, 0 ≤ y_1 < y_2 ≤ N), and result in the levels of Zombie Contamination as reported in the input.

Difficulty: interview

Starter code:

Solutions:
N = int(input())
grid = []
x1 = 50
y1 = 50
x2 = -1
y2 = -1
for y in range(N):
    grid.append(list(map(int, input())))
    for x, num in enumerate(grid[-1]):
        if num == 4:
            x1 = min(x1, x)
            y1 = min(y1, y)
            x2 = max(x2, x)
            y2 = max(y2, y)

if x1 == 51:
    print('No')
else:
    for y in range(N):
        for x in range(N):
            ex = 0
            if x1 <= x <= x2 and y1 <= y <= y2:
                ex = 4
            elif (x == x1-1 or x == x2+1) and y1 <= y <= y2:
                ex = 2
            elif (y == y1-1 or y == y2+1) and x1 <= x <= x2:
                ex = 2
            elif (x == x1-1 or x == x2+1) and (y == y1-1 or y == y2+1):
                ex = 1
            if ex != grid[y][x]:
                print('No')
                break
        else:
            continue
        break
    else:
        print('Yes')


import sys, math
def bfs(x, y):
    Q=[[x,y]]
    ptr = 0
    min_=[1000,1000]
    max_=[0,0]
    while ptr < len(Q):
        v = Q[ptr]
        ptr+=1
        x = v[0]; y=v[1]
        if matrix[x][y] == 4:
            used[x][y] = 1
            if x+1 < n:
                if used[x+1][y]==0:
                    Q.append([x+1,y])
                    used[x+1][y]=1
            if x-1 > -1:
                if used[x-1][y]==0:
                    Q.append([x-1,y])
                    used[x-1][y]=1
            if y+1 < n:
                if used[x][y+1]==0:
                    Q.append([x,y+1])
                    used[x][y+1]=1
            if y-1 > -1:
                if used[x][y-1]==0:
                    Q.append([x,y-1])
                    used[x][y-1]=1
            if x < min_[0] or (x==min_[0] and y < min_[1]):
                min_=[x,y]
            if x > max_[0] or (x==max_[0] and y > max_[1]):
                max_=[x,y]
        else:
            used[x][y]=0
    for i in range(min_[0], max_[0]+1):
        for j in range(min_[1], max_[1]+1):
            if matrix[i][j] != 4:
                print('No')
                return
    for i in range(n):
        for j in range(n):
            if used[i][j] == 0 and matrix[i][j] >= 3:
                print('No')
                return
    #print('h')
    if min_[0] > 0:
        w = min_[0] - 1
        for j in range(min_[1], max_[1]+1):
            used[w][j] = 1
            if matrix[w][j] != 2:
                print('No')
                return
    #print('h')
    if max_[0] < n-1:
        w = max_[0] + 1
        for j in range(min_[1], max_[1]+1):
            used[w][j] = 1
            if matrix[w][j] != 2:
                print('No')
                return
    if min_[1] > 0:
        w = min_[1] - 1
        for j in range(min_[0], max_[0]+1):
            used[j][w] = 1
            if matrix[j][w] != 2:
                print('No')
                return
    #print('h')
    if max_[1] < n-1:
        w = max_[1] + 1
        for j in range(min_[0], max_[0]+1):
            used[j][w] = 1
            if matrix[j][w] != 2:
                print('No')
                return
    if min_[0] > 0 and min_[1] > 0:
        x=min_[0]-1
        y=min_[1]-1
        if matrix[x][y]!=1:
            print('No')
            return
        used[x][y] =1
    if max_[0] < n-1 and max_[1] < n-1:
        x=max_[0]+1
        y=max_[1]+1
        if matrix[x][y]!=1:
            print('No')
            return
        used[x][y] =1
    if min_[0] > 0 and max_[1] < n-1:
        x=min_[0]-1
        y=max_[1]+1
        if matrix[x][y]!=1:
            print('No')
            return
        used[x][y] =1
    if max_[0] < n-1 and min_[1] > 0:
        x=max_[0]+1
        y=min_[1]-1
        if matrix[x][y]!=1:
            print('No')
            return
        used[x][y] =1
    for i in range(n):
        for j in range(n):
            if used[i][j]==1:
                continue
            elif matrix[i][j] != 0:
                print('No')
                return
    print('Yes')
            
    
n=int(input())
matrix = [[0]*n for i in range(n)]
for i in range(n):
    z=input()
    for j in range(n):
        matrix[i][j]=int(z[j])
used = [[0]*n for i in range(n)]
flag = 0
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 4:
            flag = 1
            x = i
            y = j
            break
    if flag:
        break
if not flag:
    print('No')
    return
bfs(x,y)

def main():
    size = int(input())
    sq = [[int(c) for c in input().strip()] for _ in range(size)]
    print('Yes' if haslair(sq) else 'No')
        
def haslair(sq):
    corners = [(r, c) for r, row in enumerate(sq) for c, count in enumerate(row)
                if count==1]
    if len(corners) != 4:
        return False
    left, right, top, bottom = corners[0][1], corners[3][1], corners[0][0], corners[3][0]
    if right == left + 1 or bottom == top + 1:
        return False
    for r, row in enumerate(sq):
        for c, count in enumerate(row):
            score = 3 if top < r < bottom else 1 if r in (top, bottom) else 0
            score += 3 if left < c < right else 1 if c in (left, right) else 0
            if count != (0, 0, 1, 0, 2, None, 4)[score]:
                return False
    return True

main()

def check_cell(i, j, n):
	k = 0
	if i > 1 and field[i-1][j]: k += 1
	if i < n-1 and field[i+1][j]: k += 1
	if j > 1 and field[i][j-1]: k += 1
	if j < n-1 and field[i][j+1]: k += 1
	if k < 2:
		return 0
	elif k < 4:
		return k-1
	else:
		return 4

n = int(input())
field = []

for i in range(n):
	temp = [int(x) for x in input()]
	field.append(temp)

def main():
	for i in range(n):
		for j in range(n):
			if field[i][j] and not field[i][j] == check_cell(i, j, n):
				print('No')
				return 0

	print('Yes')

main()

from sys import stdin

n = int(stdin.readline())
nn = [[int(x) for x in stdin.readline().rstrip()] for i in range(n)]

def run():
    for row in range(n):
        for col in range(n):
            if(nn[row][col] == 0):
                continue
            if(countAdj(row, col, n-1)):
                print('No')	
                return 0
    print('Yes')

def countAdj(row, col, n):
    cnt = 0
    adj = 0
    if(row > 1 and nn[row-1][col]):
        cnt += 1
        adj += nn[row-1][col]
    if(row < n and nn[row+1][col]):
        cnt += 1
        adj += nn[row+1][col]
    if(col > 1 and nn[row][col-1]):
        cnt += 1
        adj += nn[row][col-1]
    if(col < n and nn[row][col+1]):
        cnt += 1
        adj += nn[row][col+1]

    if(cnt <= 1):
        return True
    elif(cnt < 4 and nn[row][col] == cnt-1):
        if(nn[row][col] == 1 and adj != 4):
            return True
        if(nn[row][col] == 2 and not (6 <= adj <= 8)):
            return True
        return False
    elif(cnt == 4 and nn[row][col] == cnt):
        if(nn[row][col] == 4 and not (adj == 8 or adj == 10 or adj == 12 or adj == 14 or adj == 16)):
            return True
        return False
    return True

run()

n = int(input())
s = [list(map(int, input())) for _ in range(n)]
INF = 10 ** 9
x1, x2, y1, y2 = INF, -INF, INF, -INF
for i in range(n):
    for j in range(n):
        if s[i][j] != 0:
            x1, x2, y1, y2 = min(x1, i), max(x2, i), min(y1, j), max(y2, j)
need = [[0] * n for _ in range(n)]
for i in range(x1, x2 + 1):
    for j in range(y1, y2 + 1):
        if i == x1 or i == x2:
            if j == y1 or j == y2:
                need[i][j] = 1
            else:
                need[i][j] = 2
        elif j == y1 or j == y2:
            need[i][j] = 2
        else:
            need[i][j] = 4
print("Yes" if need == s else "No")


n = int(input())
aux = []
grid = []
flag = True
ans = -1
um = 0
dois = 0
quatro = 0
while(n):
        n-=1
        x = str(int(input()))
        if(x!='0'):
                aux.append(x)
for i in aux:
        txt = ''
        for j in i:
                if(j!='0'):
                        txt+=j
        grid.append(txt)
for i in grid:
        for j in i:
                if(j == '1'):
                        um+=1
                if(j == '2'):
                        dois+=1
                if(j == '4'):
                        quatro+=1
        if(ans==-1 or len(i)==ans):
                ans = len(i)
        else:
                flag = False
if(um!=4 or dois!=len(grid)*2+len(grid[0])*2-8 or quatro!=(len(grid)*len(grid[0]))-(len(grid)*2+len(grid[0])*2-4)):
        flag = False
if(flag):
        for i in range(0, len(grid)):
                if(len(grid)-i-1 < i):
                        break
                if(grid[i] != grid[len(grid)-i-1]):
                        flag = False
        for i in range(0, len(grid)):
                for j in range(0, len(grid[0])):
                        if(len(grid)-j-1 < j):
                                break
                        if(grid[i][j] != grid[i][len(grid[i])-j-1]):
                                flag = False
if(flag and ans!=-1):
        print('Yes')
else:
        print('No')


n = int(input())
aux = []
grid = []
flag = True
ans = -1
um = 0
dois = 0
quatro = 0
while(n):
        n-=1
        x = str(int(input()))
        if(x!='0'):
                aux.append(x)
for i in aux:
        txt = ''
        for j in i:
                if(j!='0'):
                        txt+=j
        grid.append(txt)
for i in grid:
        for j in i:
                if(j == '1'):
                        um+=1
                if(j == '2'):
                        dois+=1
                if(j == '4'):
                        quatro+=1
        if(ans==-1 or len(i)==ans):
                ans = len(i)
        else:
                flag = False
if(um!=4 or dois!=len(grid)*2+len(grid[0])*2-8 or quatro!=(len(grid)*len(grid[0]))-(len(grid)*2+len(grid[0])*2-4)):
        flag = False
if(flag):
        for i in range(0, len(grid)):
                if(len(grid)-i-1 < i):
                        break
                if(grid[i] != grid[len(grid)-i-1]):
                        flag = False
        for i in range(0, len(grid)):
                for j in range(0, len(grid[0])):
                        if(len(grid)-j-1 < j):
                                break
                        if(grid[i][j] != grid[i][len(grid[i])-j-1]):
                                flag = False
if(flag and ans!=-1):
        print('Yes')
else:
        print('No')
# 1523803863385


n = int(input())
aux = []
grid = []
flag = True
ans = -1
um = 0
dois = 0
quatro = 0
while(n):
        n-=1
        x = str(int(input()))
        if(x!='0'):
                aux.append(x)
for i in aux:
        txt = ''
        for j in i:
                if(j!='0'):
                        txt+=j
        grid.append(txt)
for i in grid:
        for j in i:
                if(j == '1'):
                        um+=1
                if(j == '2'):
                        dois+=1
                if(j == '4'):
                        quatro+=1
        if(ans==-1 or len(i)==ans):
                ans = len(i)
        else:
                flag = False
if(um!=4 or dois!=len(grid)*2+len(grid[0])*2-8 or quatro!=(len(grid)*len(grid[0]))-(len(grid)*2+len(grid[0])*2-4)):
        flag = False
if(flag):
        for i in range(0, len(grid)):
                if(len(grid)-i-1 < i):
                        break
                if(grid[i] != grid[len(grid)-i-1]):
                        flag = False
        for i in range(0, len(grid)):
                for j in range(0, len(grid[0])):
                        if(len(grid)-j-1 < j):
                                break
                        if(grid[i][j] != grid[i][len(grid[i])-j-1]):
                                flag = False
if(flag and ans!=-1):
        print('Yes')
else:
        print('No')