F. New Board Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Master GH-Splinter got a new board game where the board is a square grid of size $$$n$$$ and each cell of the grid contains an integer between $$$1$$$ and $$$n$$$. Each integer from $$$1$$$ to $$$n$$$ is repeated exactly $$$n$$$ times in the grid.

The grid is called $$$\it{beautiful}$$$ if both of the following conditions are met:

  1. Each row of the grid is a permutation of length $$$n$$$.
  2. Each column of the grid is a permutation of length $$$n$$$.

The game is played with one player, and he will try to make the grid $$$\it{beautiful}$$$ by making finite number of operations. In each operation, he will perform one of the following:

  • Shift all the rows one step to the right.
  • Shift all the columns one step down.

A permutation of length $$$n$$$ is a sequence of integers from $$$1$$$ to $$$n$$$ containing each number exactly once. For example, $$$[1]$$$, $$$[4,3,5,1,2]$$$, $$$[3,2,1]$$$ are permutations, and $$$[1,1]$$$, $$$[4,3,1]$$$, $$$[2,3,4$$$] are not.

Master GH-Splinter thinks this game is useful for the ninja's mind, so he wants you to train his ninja turtles on solving this problem. You're given the initial board and you should tell the ninja turtles if the board is $$$\it{beautiful}$$$ after applying $$$0$$$ or more operations.

Input

The first line of the input has one integer $$$n$$$ $$$(1 \le n \le 1000)$$$ — the size of the game board.

Each of the next $$$n$$$ lines contains $$$n$$$ integers which represent the rows of the game board $$$(1 \le a_{i,j} \le n)$$$ — $$$a_{i,j}$$$ is the $$$j$$$-th element in the $$$i$$$-th row.

Output

You have to print "YES" (without quotes) if you can make the grid $$$\it{beautiful}$$$, otherwise you have to print "NO" (without quotes).

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
3
1 2 3
3 1 2
2 3 1
Output
YES
Input
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Output
NO