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