Meeting on the Grid

Jim and Bob are trying to meet on an n×n grid. The grid is composed of cells that are either open (represented by '.') or blocked (represented by '#'). Jim starts from the top-left corner (cell (0, 0)) and Bob starts from the bottom-right corner (cell (n-1, n-1)). They can move up, down, left, or right, but cannot pass through blocked cells. They can meet if there exists a path from (0, 0) to (n-1, n-1) through open cells.

Formally, given an integer $n$ and a grid $G$ of size $n \times n$, where each cell $G[i][j]$ is defined as: [ G[i][j] = \begin{cases} '.' & \text{if the cell is open},\ '#' & \text{if the cell is blocked}, \end{cases} ]

Determine if there exists a valid path from the cell (0, 0) to the cell (n-1, n-1). Output POSSIBLE if such a path exists; otherwise, output IMPOSSIBLE.

inputFormat

The input is given from the standard input (stdin) in the following format:

The first line contains an integer $n$, indicating the size of the grid. Then follow $n$ lines, each line contains a string of length $n$, representing a row of the grid.

It is guaranteed that the first and the last characters (i.e. grid[0][0] and grid[n-1][n-1]) are open (i.e. '.').

outputFormat

Print a single line to the standard output (stdout) containing POSSIBLE if there exists a path from (0, 0) to (n-1, n-1), and IMPOSSIBLE otherwise.## sample

5
.....
.#...
.##..
.....
...#.

POSSIBLE