Puzzle

The king of Byteland received a jigsaw puzzle as a gift. The puzzle is an $n \times n$ board. The field in row $i$ and column $j$ ($1 \le i, j \le n$) has coordinates $(i, j)$ and holds a piece numbered $p(i, j)$, where $1 \le p(i, j) \le n^2$. Each number from $1$ to $n^2$ appears on exactly one piece.

Coordinates of the fields

The puzzle is solved when, for every $1 \le i, j \le n$, field $(i, j)$ holds the piece numbered $j + (i - 1) \times n$.

Only two kinds of moves are allowed:

• Row shift: cyclically shift all pieces in one row a chosen number of fields to the right.
• Column shift: cyclically shift all pieces in one column a chosen number of fields down.

Formally, shifting row $k$ to the right by $l$ fields ($1 \le l \le n-1$) turns the board into $p'(i,j) = \begin{cases} p(i,\, j+n-l) & i = k,\ j \le l \\ p(i,\, j-l) & i = k,\ j > l \\ p(i,j) & i \ne k \end{cases}$ Shifting a column down by $l$ fields is defined analogously, moving pieces toward larger row indices.

The king solved his own puzzle, but he wonders which starting configurations are solvable in the first place. Given a configuration, decide whether it can be solved using only the moves above.

The first line contains one integer $n$, the side length of the board ($2 \le n \le 200$). Each of the next $n$ lines describes the initial configuration; line $i+1$ contains $p(i, 1), p(i, 2), \ldots, p(i, n)$ separated by single spaces. The values form a permutation of $1 \ldots n^2$.

Print a single line: YES if the board can be solved using the allowed moves, or NO otherwise.

A sequence of row shifts and column shifts turns one configuration into another, as illustrated below.