008 - Hokkaido

問題

学生である山本くんは、$N \times N$ の正方形の形をした島「Hokkaido」に住んでいる。
この島では、気温の低さと海水が原因で、至る所が凍ってしまうことがある。
山本くんは、地面が凍っていると進む方向を変えることができないため、学校に辿り着けるか心配である。
ここで、北から $y$、 西から $x$ 進んだ地点 $(1 \leq y, x \leq N)$ を $(y, x)$ と表したとき、凍っている地点 $(y, x)$ について、「進む方向を変えることができない」とは、以下のことを表す。

• $(y - 1, x)$ から $(y, x)$ に来た場合、$(y + 1, x)$ にしか進むことができない。
• $(y + 1, x)$ から $(y, x)$ に来た場合、$(y - 1, x)$ にしか進むことができない。
• $(y, x - 1)$ から $(y, x)$ に来た場合、$(y, x + 1)$ にしか進むことができない。
• $(y, x + 1)$ から $(y, x)$ に来た場合、$(y, x - 1)$ にしか進むことができない。

また、凍っていない地点 $(y, x)$ では、どこから来たとしても、$(y - 1, x)$, $(y + 1, x)$, $(y, x - 1)$, $(y, x + 1)$ のどの地点にも進むことができる。

現在の島の状況が与えられるので、あなたには山本くんが学校に辿り着くことができるのか調べてほしい。
なお、山本君は最初、山本君の家におり、山本君の家がある地点と学校がある地点の地面は凍っていない。
また、島の周りは海で囲まれているため、島の外側を通っていくことはできない。

入力

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

$N$
$S_{1,1}$ $\ldots$ $S_{1,N}$
$\vdots$
$S_{N,1}$ $\ldots$ $S_{N,N}$

$S_{y, x}$ が

• . のとき、地点 $(y, x)$ の地面が凍っていないことを表す。
• # のとき、地点 $(y, x)$ の地面が凍っていることを表す。
• S のとき、地点 $(y, x)$ に山本くんの家があることを表す。
• G のとき、地点 $(y, x)$ に学校があることを表す。

出力

山本くんが学校に辿り着けるのならば Possible、辿り着けないのならば Impossible と出力せよ。
出力の最後には改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $3 \leq N \leq 500$
• $S_{y, x}$ は .,#,S,G のいずれかである
• 山本くんの家と学校はそれぞれ一つずつである

入出力例

入力例1

5
S##.#
#.##.
#####
..###
###.G

出力例1

Possible

解説

$(1, 1) → (1, 4) → (5, 4) → (5, 5)$ などのルートで学校に到着できる。

入力例2

5
S###.
#####
##G##
#####
.###.

出力例2

Impossible