D - FU 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MiB

問題文

X さんとY さんはFUという名前のゲームで遊んでいます。


このゲームは、縦横ともに長さ n で n \times n 個の正方形のマスに区切られた盤面とFUという駒を用いて行われ、X さんは盤面の最上行の各マスに 1 つずつ自分のFUを下向きに、Y さんは盤面の最下行の各マスに 1 つずつ自分のFUを上向きに置いたところから始まります。


プレイヤーは以下のルールに従い、交互に自分のFUをひとつ選んで移動させるということを繰り返します。

  • X さんのFUは、現在置かれているマスの下に隣接するマスへしか移動できません
  • Y さんのFUは、現在置かれているマスの上に隣接するマスへしか移動できません
  • 自分のFUを相手のFUと同一マスに置くことで、相手のFUを取ります

このゲームでは、自分の手番をパスすることや、二度続けて自分のFUを動かすことはできません。相手のFUをすべて取ったプレイヤーが勝ちです。


ぬまくんさんは X さんと Y さんの試合を途中から観戦したのですが、どちらが先手か聞いても、X さんと Y さんは試合に深く集中しているため、答えてくれません。幸い、試合は始まったばかりでどちらも相手のFUを取っていないので、盤面の状態からどちらが先手かわかるかもしれません。


そこで、現在の盤面の状態を入力に受け取って、どちらが先手かを求めるプログラムを作成してください。

入力

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

n
B_{1,1}B_{1,2}...B_{1, n}
B_{2,1}B_{2,2}...B_{2, n}
...
B_{n,1}B_{n,2}...B_{n, n}
  • 1 行目には、盤面の一辺あたりの大きさを表す整数 n (2 \leq n \leq 100) が与えられる。
  • 続く n 行には、盤面の各行の情報が最上行から最下行にかけて順に与えられる。
  • B の各要素はマスの状態を表しており、.、X、Yのいずれかの文字からなる。
  • .はそのマスに何も駒が置かれていないことを意味し、XとYはそれぞれ X さん、Y さんのFUがそのマスにあることを意味する。
  • 各列において、必ずXとYが一つずつ存在しており、また、必ずXがYよりも上の行に位置することが保証される。
  • 入力として与えられる盤面は、ゲームのルールと矛盾しないことが保証される。

出力

X さんが先手の場合はXを、Y さんが先手の場合はYを 1 行で出力せよ。

また、どちらが先手か決められない場合はImpossibleと 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

4
X..X
.XX.
.YYY
Y...

出力例1

Y

入力例2

3
XXX
...
YYY

出力例2

Impossible