这道题原本是 Juan 关于 1997 年南非 IOI 的历史课。然而，这堂课被委员会的其他成员删去了，于是你看到了下面的题面：

Abraham 是一位勇敢的探险家，他要前往从未有程序员到过的地方。在下一次探险中，他计划探索一座非常奇特的迷宫。他知道，迷宫是一个 $n \times n$ 的网格，每个格子里都有一个箭头。每个箭头指向上、下、左、右四个方向之一。如果 Abraham 踏入某个格子，他就必须从该格子开始沿着箭头前进。每个箭头都会使 Abraham 向它所指的方向移动一个格子；如果他到达一个指向迷宫外的箭头，就能逃出迷宫。

Abraham 不知道迷宫中箭头的朝向，但他还有其他信息。在他的迷宫地图上，有些格子被涂成黑色，其他格子被涂成白色。他相信，如果从任意一个黑色格子出发，他永远无法逃出迷宫；如果从任意一个白色格子出发，他最终都能逃出迷宫。

Abraham 的猜想可能是错的：存在某些黑白格子的布局，使得无论箭头如何朝向，上述条件都无法对所有格子同时成立。下图展示了一个例子。

这张地图表示一座迷宫，其中白色格子可以满足 Abraham 的猜想。从任意一个白色格子出发，图中所示的箭头都会引导他离开迷宫；但是，无论如何设置未画出的箭头的朝向，都不可能使他从黑色格子出发时一直被困在迷宫中。

Abraham 请你帮助他判断：给定地图上格子的涂色方式，是否存在一种箭头朝向的安排，使网格中每个格子，无论黑色还是白色，都符合他的猜想。

输入格式

• 第一行包含一个正整数 $n$。
• 接下来 $n$ 行，每行包含 $n$ 个字符，每个字符为 0 或 1。0 表示黑色格子，1 表示白色格子。这 $n$ 行描述了整个网格。

输出格式

如果能安排箭头的朝向，使 Abraham 从任意黑色格子出发时永远无法逃出迷宫，而从任意白色格子出发时最终都能逃出迷宫，输出 SI。

如果不可能，输出 NO。

样例

输入格式 1

3
001
001
111

输出格式 1

SI

输入格式 2

2
01
10

输出格式 2

NO

说明

第一个样例对应下面的涂色方式（左图），以及一种可行的箭头朝向安排：

第二个样例就是题目故事中提到的例子，要求的条件无法对所有格子同时成立。

数据范围

• $2 \le n \le 1000$。

子任务

• 子任务 1（10 分）：$n=2$。
• 子任务 2（25 分）：保证黑色格子构成一个连通区域，且迷宫至少有两个角落是黑色。
• 子任务 3（25 分）：保证白色格子构成一个连通区域，且黑色格子的数量少于 $4n-4$。
• 子任务 4（40 分）：没有额外限制。

说明

如果一个格子集合中的任意两个格子之间，都存在一条只经过该集合中格子的路径，且每一步都在共用一条边的格子之间移动，就称该集合构成一个连通区域。特别地，如果任意两个黑色格子之间都存在一条只由黑色格子组成的路径，那么黑色格子构成一个连通区域。类似地，如果任意两个白色格子之间都存在一条只由白色格子组成的路径，那么白色格子构成一个连通区域。

在第一个样例中，白色格子和黑色格子各自都构成一个连通区域。

在第二个样例中，黑色格子不构成一个连通区域，因为它们之间的任何路径都会经过白色格子。