Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by n square grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and a_{x}, y ≠ 1, there should exist two indices s and t so that a_{x}, y = a_{x}, s + a_{t}, y, where a_{i}, j denotes the integer in i-th row and j-th column.

Help Okabe determine whether a given lab is good!


-----Input-----

The first line of input contains the integer n (1 ≤ n ≤ 50) — the size of the lab. 

The next n lines contain n space-separated integers denoting a row of the grid. The j-th integer in the i-th row is a_{i}, j (1 ≤ a_{i}, j ≤ 10^5).


-----Output-----

Print "Yes" if the given lab is good and "No" otherwise.

You can output each letter in upper or lower case.


-----Examples-----
Input
3
1 1 2
2 3 1
6 4 1

Output
Yes

Input
3
1 5 2
1 1 1
1 2 3

Output
No



-----Note-----

In the first sample test, the 6 in the bottom left corner is valid because it is the sum of the 2 above it and the 4 on the right. The same holds for every number not equal to 1 in this table, so the answer is "Yes".

In the second sample test, the 5 cannot be formed as the sum of an integer in the same row and an integer in the same column. Thus the answer is "No".

Difficulty: interview

Starter code:

Solutions:
N = int(input())
table = []
for i in range(N):
    table.append(list(map(int, input().split())))

for i in range(N):
    for j in range(N):
        if table[i][j] == 1:
            continue
        flg = False
        for s in range(N):
            for t in range(N):
                if table[i][j] == table[i][s] + table[t][j]:
                    flg = True
                    break
        if not flg:
            print("No")
            return
print("Yes")


I = lambda : map(int, input().split())
n, = I()
arr = []
for i in range(0, n):
    arr.append(list(I()))

for x in range(0, n):
    for y in range(0, n):
        if arr[x][y] != 1:
            found = False
            for s in range(0, n):
                for t in range(0, n):
                    if arr[x][y] == arr[x][s] + arr[t][y]:
                        found = True
            if not found:
                print("No")
                return
print("Yes")

def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))
    for i in range(n):
        for j in range(n):
            e = a[i][j]
            if e == 1:
                continue
            else:
                fl = False
                for i1 in range(n):
                    for j1 in range(n):
                        if a[i1][j] + a[i][j1] == e:
                            fl = True
                            break
                    if fl:
                        break
                if fl:
                    continue
                else:
                    print('No')
                    return
    print('Yes')

main()

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
ok = True
for i in range(n):
    for j in range(n):
        if a[i][j] != 1:
            check = False
            for k in range(n):
                for l in range(n):
                    if a[i][j] == a[i][k] + a[l][j]:
                        check = True
                    if check:
                        break
                if check:
                    break
            ok &= check
print("Yes" if ok else "No")


n = int(input())
s = []
for k in range(n):
    s.append([int(i) for i in input().split()])
t = 0
for i in range(n):
    for j in range(n):
        l = 0
        if s[i][j] !=1:
            for x in range(n):
                for y in range(n):
                    if s[i][x]+ s[y][j] == s[i][j]:
                        l = 1
            if not l:
                t = 1
if t:
    print("No")
else:
    print("Yes")


from sys import stdin, stdout

def main():
    n = int(stdin.readline())
    mat = []
    for i in range(n):
        mat.append(list(map(int, stdin.readline().split())))
    for i in range(n):
        for j in range(n):
            st = True
            for u in range(n):
                for k in range(n):
                    if mat[i][j] == 1 or mat[i][j] == mat[u][j] + mat[i][k]:
                        st = False
                        break
                if not st: break
            if st:
                return False
    return True


print('Yes' if main() else 'No')


import sys 

def main():
    n = int(input())
    x = []
    for i in range(n):
        y = list(map(int,sys.stdin.readline().split()))
        x.append(y)

    for i in range(n):
        for j in range(n):
            if x[i][j] == 1:
                continue
            found = False
            for o in range(n):
                a = x[i][o]
                if o == j:
                    continue
                for p in range(n):
                    if p ==i:
                        continue
                    b = x[p][j]
                    if a+b == x[i][j]:
                        found = True
                        break
                if found:
                    break
            if not found:
                print("No")
                return
    print("Yes")
    

main()


n = int(input())
data = []
for i in range(n):
    data += [list(map(int, input().split()))]

for i in range(n):
    for j in range(n):
        if data[i][j] == 1:
            t = True
            continue
        t = False
        for k in range(n):
            for m in range(n):
                if data[i][k] + data[m][j] == data[i][j]:
                    t = True
                    break
        if not t:
            print("No")
            break
    if not t:
        break
if t:
    print("Yes")


def check(r, c, x):
    rtn = False
    rs = [a[r][i] for i in range(n) if i != c]
    cs = [a[i][c] for i in range(n) if i != r]
    for r in rs:
        for c in cs:
            if r + c == x:
                rtn = True
                break
    return rtn

n = int(input())
a = [list(map(int, input().split()))for _ in range(n)]

ans = True
for i in range(n):
    for j in range(n):
        if a[i][j] != 1:
            ans &= check(i, j, a[i][j])

print('Yes' if ans else 'No')


def solve(g):
    for i in range(n):
        for j in range(n):
            if g[i][j] == 1:continue
            for p in range(n):
                for q in range(n):
                    if p == i or q == j:continue
                    if g[i][q] + g[p][j] == g[i][j]:break
                else:
                    continue
                break
            else:
                return "No"
    return "Yes"

n = int(input())

g = []

for i in range(n):
    g.append([int(item) for item in input().split()])
    
print(solve(g))

#! python3

def is_good(a, n, i, j):
    c = set([])
    for x in range(n):
        c.add(a[i][j] - a[i][x])
    for x in range(n):
        if a[x][j] in c:
            return True
    return False

n = int(input())
a = []
for _ in range(n):
    a.append([int(x) for x in input().strip().split(' ')])

good = True
for i in range(n):
    for j in range(n):
        if a[i][j] != 1 and not is_good(a, n, i, j):
            good = False
            break
if good:
    print("Yes")
else:
    print("No")


#!/usr/bin/env python3
import sys

def main():
    n = int(sys.stdin.readline())
    mat = [None for __ in range(n)]
    for indx in range(n):
        mat[indx] = list(map(int, sys.stdin.readline().split()))

    good = True
    for row in range(n):
        for col in range(n):
            if mat[row][col] == 1:
                continue
            else:
                good &= check_this_element(mat, row, col)
    if good:
        print("Yes")
    else:
        print("No")

def check_this_element(mat, row, col):
    n = len(mat)
    for _row in range(n):
        for _col in range(n):
            if mat[_row][col] + mat[row][_col] == mat[row][col]:
                return True
    return False

def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
from sys import stdin, stdout

def rint():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()


def check(i, j):
    for r in range(n):
        for c in range(n):
           if a[i][c] + a[r][j] == a[i][j]:
               return 1
    return 0
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
    a[i] = list(rint())

for i in range(n):
    for j in range(n):
        if a[i][j] == 1:
            continue
        if check(i,j) == 0:
            print("No")
            return

print("Yes")





def int_input():
    return list(map(int, input().split()))


n = int(input())
matr = [list(int_input()) for i in range(n)]

good = True
for row in range(n):
    nums = set(matr[row])
    for col in range(n):
        num = matr[row][col]
        if num == 1:
            continue
        cur_good = False
        for i in range(n):
            cur_good |= num - matr[i][col] in nums
        good &= cur_good

print('Yes' if good else 'No')


#def proverka(b, k, m, p):
#  for i in range()

n = int(input()) 
a = []
for i in range(n):
    a.append([int(j) for j in input().split()])
flag = "Yes" 
for i in range(n):
  for j in range(n):
    if(a[i][j] != 1):
      f = False
      for k in range(n):
        if(f):
          break
        for z in range(n):
          if(a[k][j] + a[i][z] == a[i][j]):
            f = True
          if(f):
            break
      if(not(f)):
        flag = "No"

print(flag)

n=int(input())
a=[[0]*n for i in range(n)]
f=True
d=True
for i in range(n):
    a[i]=list(map(int,input().split(" ")))
for i in range(n):
    for j in range(n):
        s=a[i][j]

        if s!=1:
            f = False
            for t in range(n):
                if t!=i:
                    x=s-a[t][j]
                    if x in a[i]:
                        f=True
        if f==False:
            d=False
if not d:
    print('No')
else:
    print('Yes')

n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
for i in range(n):
	for j in range(n):
		c=0
		if a[i][j]==1:
			continue
		for k in range(n):
			for l in range(n):
				if a[i][j]==a[i][k]+a[l][j]:
					c=1
					break
			if c:
				break
		if not c:
			print('No')
			return
print('Yes')


a = [list(map(int, input().split())) for i in range(int(input()))]
n = len(a)
for i in range(n):
    for j in range(n):
        if a[i][j] != 1:
            found = False
            for i2 in range(n):
                for j2 in range(n):
                    if a[i][j] == a[i][j2] + a[i2][j]:
                        found = True
            if not found:
                print('No\n')
                return
print('Yes')

n = int(input())
a = []
for i in range(n):
	a.append([int(x) for x in input().split()])
for i in range(n):
	for j in range(n):
		if a[i][j]==1:
			continue
		val = False
		for k in range(n):
			for l in range(n):
				if (a[i][k]+a[l][j]==a[i][j]):
					val = True
		if val==False:
			print("No")
			return
print("Yes")
				
		


from itertools import *
n=int(input())
f=[list(map(int,input().split())) for _ in range(n)]
for i,j in product(list(range(n)),list(range(n))):
    x=f[i][j]
    if x==1: continue
    if not any(a+b==x for a, b in product(chain(f[i][:j], f[i][j+1:]),(f[k][j] for k in chain(list(range(i)), list(range(i+1,n)))))):
        print("No")
        return
print("Yes")


def fin(s, row, column):
	for i in row:
		for j in column:
			if i+j == s:
				return True
	return False

n = int(input())
a = []
for i in range(n):
	k = input().split(' ')
	k = list(map(int,k))
	a.append(k)

ans = True

for i in range(n):
	for j in range(n):
		if a[i][j] == 1:
			continue
		else:
			s = a[i][j]
			row = a[i]
			column = []
			for t in range(n):
				column.append(a[t][j])
			ans = fin(s,row,column)
			if ans == False:
				break
	if ans == False:
		break

if ans==True:
	print("Yes")
else:
	print("No")


import sys

def is_good(lab):
  n = len(lab)
  for i in range(n):
    for j in range(n):
      v = lab[i][j]
      if v > 1 and all(x + y != v for x in lab[i] for y in (lab[k][j] for k in range(n))):
        return False
  return True

n = int(input())

lab = [[int(i) for i in input().split()] for _ in range(n)]

print('Yes' if is_good(lab) else 'No')


n = int(input())
tbl = []
for i in range(n):
    tbl.append(list(map(int, input().split())))

out = False
for i, row in enumerate(tbl):
    for j in range(len(row)):
        out = False
        e = row[j]
        if e == 1:
            out = True
            continue
        for j1, e1 in enumerate(row):
            if j1 != j:
                for i1 in range(n):
                    if e1 + tbl[i1][j] == e:
                        out = True
                        break
            if out:
                break
        if not out:
            print('No')
            break
    if not out:
        break
if out:
    print('Yes')