Problem Description

Takahashi the Squid loves painting the floor. The floor is divided into an $N \times N$ grid, and some cells (possibly zero) have obstacles. Takahashi wants to paint the floor following these rules:

• Repeat the action of "painting the current cell and moving to one of the adjacent cells (up, down, left, or right)".
• Rotate the direction by $ 90 $ degrees each time you move. That is, after moving up or down, you must move right or left next, and after moving right or left, you must move up or down next.
• Do not move to a cell that has already been painted.
• Do not move to a cell outside the grid or a cell with an obstacle.

Takahashi has already decided which cell to start from. Can he paint all the cells without obstacles by moving wisely? There are no specific requirements for the direction of the first move or the last cell to paint. Also, there is no need to move after painting the last cell.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N\ (2 \leq N \leq 400)$, representing the number of cells on one side of the grid.

• The next $ N $ lines contain the grid information. The $i\ (1 \leq i \leq N)$ line contains a string $ S_i $ of length $ N $. The $j\ (1 \leq j \leq N)$ character of this string represents the cell at row $ i $ and column $ j $ as follows:

• . indicates a floor cell.

• # indicates a cell with an obstacle.
• s indicates a floor cell that Takahashi has decided to start from.

It is guaranteed that there is exactly one s in these strings and at least one . exists.

Output Format

Output POSSIBLE if it is possible to paint all the cells without obstacles, otherwise output IMPOSSIBLE. End the output with a newline.

Sample Input and Output

Sample Input #1

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

Sample Output #1

POSSIBLE

Sample Input #2

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

Sample Output #2

IMPOSSIBLE

Sample Input #3

3
..#
.s.
#..

Sample Output #3

IMPOSSIBLE

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset $ 1 $ where $N \leq 50$, you will be awarded $ 40 $ points.
• If you solve all the test cases, you will be awarded an additional $ 60 $ points.

Sample Explanation 1

You can move as shown in the figure to paint the cells.

见题面 Input 部分

见题面 Output 部分