この問題は、南アフリカで開催された 1997 年の IOI についての Juan の歴史の授業になる予定でした。しかし、その授業は委員会の他のメンバーによる検閲を受け、結果として次の問題文があなたのもとに届きました。

Abraham は、プログラマーがまだ誰も足を踏み入れたことのない場所へ向かう勇敢な探検家です。次の探検では、とても奇妙な迷路を調べようとしています。迷路は $n \times n$ のマス目で、各マスに矢印が 1 つあることを知っています。各矢印は、上、下、左、右の 4 方向のいずれかを指しています。Abraham があるマスに足を踏み入れると、そのマスから矢印に従って進まなければなりません。各矢印は、その指す方向へ Abraham を 1 マス移動させます。迷路の外を指す矢印に到達すれば、脱出できます。

Abraham は迷路の矢印の向きを知りませんが、別の情報を持っています。彼の迷路の地図では、一部のマスは黒く、他のマスは白く塗られています。彼は、どの黒いマスから出発しても決して迷路から脱出できず、どの白いマスから出発しても最終的に脱出できると考えています。

Abraham の仮定は間違っているかもしれません。矢印をどのように向けても、すべてのマスについて同時に指定の条件を満たすことができない白黒の配置があるのです。次の図に一例を示します。

この地図が表す迷路では、白いマスについて Abraham の仮定を満たすことができます。そのどちらから出発しても、図の矢印によって迷路の外に出ます。しかし、描かれていない矢印をどのように向けても、黒いマスから出発したときに閉じ込められたままにすることは不可能です。

Abraham は、地図上のマスの塗り方が与えられたとき、黒いマスも白いマスも含めて、マス目のすべてのマスで彼の考えに一致する矢印の配置が存在するかどうかを判定する手助けを求めています。

入力

• 1 行目には、正の整数 $n$ が与えられます。
• 続く $n$ 行には、それぞれ 0 または 1 の $n$ 文字が与えられます。0 は黒いマス、1 は白いマスを表します。この $n$ 行がマス目を表します。

出力

黒いマスから出発すると Abraham が決して脱出できず、白いマスから出発すると最終的に脱出できるように矢印を向けられる場合、SI を出力してください。

不可能な場合、NO を出力してください。

入出力例

入力 1

3
001
001
111

出力 1

SI

入力 2

2
01
10

出力 2

NO

注記

最初の入出力例に対応する塗り方（左側）と、可能な矢印の向きの配置を以下に示します。

2 番目の入出力例は、すべてのマスについて同時に要求された条件を満たせない例として、問題文の物語で述べたものです。

制約

• $2 \le n \le 1000$。

小課題

• 小課題 1（10 点）：$n=2$。
• 小課題 2（25 点）：黒いマスは連結な領域をなすことが保証され、迷路の少なくとも 2 つの角が黒いマスです。
• 小課題 3（25 点）：白いマスは連結な領域をなすことが保証され、黒いマスの数は $4n-4$ 未満です。
• 小課題 4（40 点）：追加の制約はありません。

注記

マスの集合について、その任意の 2 マスの間に、辺を共有するマスどうしを移動し、その集合のマスのみを通る経路が存在するとき、その集合は連結な領域をなすといいます。特に、任意の 2 つの黒いマスの間に黒いマスだけからなる経路が存在するとき、黒いマスは連結な領域をなします。同様に、任意の 2 つの白いマスの間に白いマスだけからなる経路が存在するとき、白いマスは連結な領域をなします。

最初の入出力例では、白いマスも黒いマスもそれぞれ連結な領域をなします。

2 番目の入出力例では、黒いマスの間のどの経路も白いマスを通るため、黒いマスは連結な領域をなしません。