You are given an n \times n matrix that contains the numbers 1,\ \dots,\ n^2. The number at the intersection of the i-th row and j-th column is a_{i,j}. Your task is to sort the matrix by performing any of the following operations arbitrarily many times:

1. Pick two rows and swap them.
2. Pick two columns and swap them.

The matrix is considered sorted is for each pair cells (x1, y1), (x2, y2) it holds that a_{x1,y1} > a_{x2,y2} if x1 > x2. If x1 = x2 then a_{x1,y1} > a_{x2,y2} if y1 > y2. That is, sort the matrix like this:

1 2 3
4 5 6
7 8 9

Input

The first line contains a single integer n: The size of the matrix.
The following n lines describe the matrix: each line contains n integers.

Output

Print "Yes" if the matrix can be sorted and "No" otherwise.

Constraints

• 1 \leq n \leq 100

Example 1

Input:

1
1

Output:

Yes

Example 2

Input:

3
6 5 4 
3 2 1 
9 8 7 

Output:

Yes

Example 2

Input:

4
6 8 13 11 
3 15 16 4 
7 5 1 12 
2 9 14 10

Output:

No