问题描述

小高橋喜欢涂地板。地板被分割成了一个 $N \times N$ 的网格，其中有一些格子上有障碍物（可能没有）。 小高橋打算按照以下规则来涂地板：

• 反复执行以下动作："涂当前所在的格子，然后移动到上下左右相邻的格子"。
• 每次移动都要旋转 $90$ 度。也就是说，如果向上或向下移动后，下一步会向右或向左移动；如果向右或向左移动后，下一步会向上或向下移动。
• 不会移动到已经涂过的格子上。
• 不会移动到网格外或有障碍物的格子上。

小高橋已经决定从哪个格子开始。这时候，小高橋能够巧妙地移动涂地板，将没有障碍物的所有格子都涂满吗？注意，没有特别要求起始时的移动方向或最后一个涂的格子。此外，涂完最后一个格子后不需要再移动。

输入

输入以以下格式给出。

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

• 第 $1$ 行是一个整数 $N (2 ≦ N ≦ 400)$，表示网格的边长。

• 接下来的 $N$ 行描述了网格的信息。其中第 $i$ 行（$1 ≦ i ≦ N$）是一个长度为 $N$ 的字符串 $S_i$，表示第 $i$ 行第 $j$ 列（$1 ≦ j ≦ N$）的格子信息。

  • 如果是 .，表示这个格子是地板。
  • 如果是 #，表示这个格子有障碍物。
  • 如果是 s，表示这个格子是地板，并且这是小高橋决定开始的位置。

保证在这些字符串中会恰好出现 $1$ 个 s，至少有一个 .。

部分分

本问题设置了部分分。

• 对于满足 $N ≦ 50$ 的数据集 $1$，如果通过测试，则得到 $40$ 分。

• 如果通过全部测试用例，则额外得到 $60$ 分。

输出

如果可以将所有格子都涂满，则输出 POSSIBLE；否则输出 IMPOSSIBLE。输出末尾要有换行符。

示例输入1

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

示例输出1

POSSIBLE

只需要按照图示移动并涂色即可。

示例输入2

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

示例输出2

IMPOSSIBLE

示例输入3

3
..#
.s.
#..

示例输出3

IMPOSSIBLE