神秘浮石矩阵

题目描述

在「重力神殿」中，供奉着一块 n×n 的神秘浮石矩阵。浮石由具有法力编号的石块组成，而空位则以“0”表示。神殿自建成以来便遵循着一个永恒法则：

任何浮石矩阵都必须呈现出由左上向右下逐步扩展的阶梯形结构。(如下图)

正式的，给定一个 n × n 的矩阵，矩阵满足每一行在右侧有若干个零（视为空位），且随着行号增加，非零元素的个数不减（下方行不会比上方行有更少的非零元素）。

据祭司所述，浮石矩阵在每个“时刻跳动”中都会经历一次固定的变换：

1. 整块矩阵在空中缓缓顺时针旋转 90 度；
2. 随后，所有带有法力的石块便如受重力牵引一般，沿列方向向下堆叠，留出上方的空位。

示例：

随着时间流逝，矩阵的形态不断变化。神殿的学者们坚信： 每一个合法矩阵都将在若干次时刻跳动后回到初始形态，形成某种神圣的周期。

旅者，你的使命是验证这一信念： 给定一块浮石矩阵，你需要判断它是否可能在有限次操作后重返最初的排列。

输入格式

第一行一个整数 n (1 ≤ n ≤ 1000)。

接下来 n 行，每行 n 个整数，0 表示空格，其他整数为方块编号，方块编号保证在int范围内。矩阵保证满足题中的阶梯型性质。

输出格式

若存在正整数 t 使得经过 t 次操作矩阵回到初始状态，输出 YES；否则输出 NO。

样例 1

2
1 0
2 1

YES

样例 2

4
0 0 0 0
1 0 0 0
3 2 5 0
9 4 7 10

YES