You are given a grid of size $n \times n$ whose each element is an integer between $1$ and $n$.

Your task is to find out if every row and column contains $n$ distinct values.

Input

The first line contains an integer $n$: the size of the grid.

After this, there are $n$ lines which describe the grid. Each line has $n$ integers between $1$ and $n$.

Output

Print YES if every row and column contsina $n$ distinct values and NO otherwise.

Constraints

• $1 \le n \le 100$

Example 1

Input:

3
1 2 3
2 3 1
3 1 2

Output:

YES

Example 2

Input:

3
1 1 1
1 1 1
1 1 1

Output:

NO