Right Angle Painting

Takahashikun likes to paint floors. The floor is an $N \times N$ grid, and some cells (possibly none) contain obstacles.

The grid is given as $N$ strings $S_1, \ldots, S_N$. The $j$-th character of $S_i$ describes cell $(i, j)$: '.' and 's' are empty cells, and '#' is a cell with an obstacle.

Exactly one cell contains 's'. Takahashikun enters that cell and paints it. Then he makes zero or more steps by these rules:

• Each step moves to one of the four adjacent cells (up, down, left, right) and paints it.
• Except for the first step, the direction must change by 90 degrees from the previous step. After a horizontal move he must move vertically, and vice versa.
• He must not enter an already painted cell.
• He must not enter an obstacle.
• He must not leave the grid.

$N$ $S_1$ $S_2$ $\vdots$ $S_N$

Print "POSSIBLE" if he can paint all cells without obstacles. Otherwise print "IMPOSSIBLE".

• $1 \leq N \leq 400$
• $|S_i| = N$
• Each character of $S_i$ is '.', '#', or 's'.
• There is exactly one 's'.
• There is at least one '.'.