퍼즐

바이트랜드(Byteland)의 왕이 선물로 조각 퍼즐을 받았다. 퍼즐은 $n \times n$ 크기의 판으로 이루어져 있다. $i$번째 행, $j$번째 열($1 \le i, j \le n$)의 칸은 좌표 $(i, j)$를 가지며, 번호 $p(i, j)$인 조각이 놓여 있다($1 \le p(i, j) \le n^2$). $1$부터 $n^2$까지의 각 번호는 정확히 한 조각에만 적혀 있다.

칸의 좌표

모든 $1 \le i, j \le n$에 대해 칸 $(i, j)$에 번호 $j + (i - 1) \times n$인 조각이 놓이면 퍼즐이 완성된다.

다음 두 가지 이동만 허용된다.

• 행 이동: 한 행의 모든 조각을 원하는 칸 수만큼 오른쪽으로 순환 이동한다.
• 열 이동: 한 열의 모든 조각을 원하는 칸 수만큼 아래쪽으로 순환 이동한다.

정확히는, $k$번째 행을 오른쪽으로 $l$칸($1 \le l \le n-1$) 순환 이동하면 판은 다음과 같이 바뀐다. $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}$ 열을 아래로 $l$칸 순환 이동하는 것도 같은 방식으로 정의되며, 조각을 더 큰 행 번호 쪽으로 옮긴다.

왕은 자신의 퍼즐을 풀었지만, 애초에 어떤 처음 배치가 완성 가능한지 궁금해한다. 주어진 배치가 위의 이동만으로 완성될 수 있는지 판정하여라.

첫째 줄에 판 한 변의 길이인 정수 $n$이 주어진다($2 \le n \le 200$). 이어지는 $n$개의 줄에 처음 배치가 주어진다. $i+1$번째 줄에는 $p(i, 1), p(i, 2), \ldots, p(i, n)$이 공백 하나로 구분되어 주어진다. 이 값들은 $1 \ldots n^2$의 순열이다.

배치를 완성할 수 있으면 YES를, 완성할 수 없으면 NO를 한 줄에 출력한다.

아래 그림처럼 행 이동과 열 이동을 연달아 적용하면 한 배치를 다른 배치로 바꿀 수 있다.