Migrated from Lutece 1865 矩阵

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你有一个n行和n列的矩阵。定义两个单元格(a,b)(c,d)位于同一对角线当且仅当(c-a)=(d-b)

每个对角线的第一个单元将按照(n,1)(n-1,1)...(1,1)(1,2)...(1,n)的顺序排列。

您需要从每个对角线中选择一个数字。 满足所有2 * n-1个数字必须是两两不同的。

Input

第1行一个整数n

第2行到第n+1行，每行n个整数，代表这个矩阵

Output

如果不能满足条件，请输出NO，否则输出YES

Samples

2
1 1
1 1

NO

2
1 2
1 3

YES

Note

n<=300 1<=矩阵元素<=1e9

Resources

每周一题 Div. 1