問題文

イカの高橋君は床を塗るのが大好きです。床は $N \\times N$ のマス目状に区切られており、いくつか（$0$ 個もありうる）のマスには障害物があります。高橋君はこの床を以下のルールで塗ろうと考えています。

• 「今いるマスの床を塗って、上下左右いずれかの隣のマスに移動する」という行動を繰り返す。
• 移動するたびに向きを $90$ 度回転する。すなわち、上または下に移動した直後には右または左に移動し、右または左に移動した直後には上または下に移動する。
• すでに塗ったマスには移動しない。
• マス目の外や障害物のあるマスには移動しない。

高橋君は、すでにどのマスからスタートするかを決めています。このとき、高橋君はうまく移動しながら床を塗ることで、障害物のない全てのマスを塗ることが可能でしょうか。ただし、スタート直後の移動方向や最後に塗るマスには特に指定はありません。また、最後のマスを塗った直後には移動する必要はありません。

入力

入力はイカの形式で標準入力から与えられる。

$N$ $S_1$ $S_2$ : $S_N$

• $1$ 行目には、マス目の $1$ 辺の個数を表す整数 $N (2 ≦ N ≦ 400)$ が与えられる。

• $2$ 行目からの $N$ 行には、マス目の情報が与えられる。このうち $i (1 ≦ i ≦ N)$ 行目には、長さ $N$ の文字列 $S_i$ が与えられる。このうち $j (1 ≦ j ≦ N)$ 文字目は、$i$ 行目 $j$ 列目のマスの情報を以下のように表す。

  • . の場合：このマスが床であることを表す。
  • # の場合：このマスに障害物があることを表す。
  • s の場合：このマスは床であり、高橋君がスタートしようと決めているマスであることを表す。

  ただし、これらの文字列の中には s がちょうど $1$ つ存在すること、. が少なくとも $1$ つ以上存在することが保証される。

部分点

この問題には部分点が設定されている。

• $N ≦ 50$ を満たすデータセット $1$ に正解した場合は、$40$ 点が与えられる。
• 全てのテストケースに正解した場合は、上記とは別に $60$ 点が与えられる。

出力

全てのマスを塗ることが可能ならば POSSIBLE、そうでない場合は IMPOSSIBLE を $1$ 行に出力せよ。出力の末尾に改行を入れること。

入力例1

5
#....
..s..
..#..
#....
##..#

出力例1

POSSIBLE

図のように移動しながら塗れば良いです。

入力例2

5
s.###
..###
###..
#....
#..##

出力例2

IMPOSSIBLE

入力例3

3
..#
.s.
#..

出力例3

IMPOSSIBLE