← 返回题目列表

AtCoder · code_festival_relay_d

D. 福

中文机器翻译题面 查看原题

問題文

X先生和Y先生 我正在玩一个名为FU的游戏。


这个游戏又长又宽。 n 一块板分为 n \times n 方形单元格和 该游戏使用名为FU的棋子进行,Mr. 1 各有各的 Y 先生将FU面朝下放置在棋盘底行的每个方格中。 首先将 1 各有各的 Y 先生将FU面朝上放置。


玩家按照以下规则轮流进行 重复选择一个FU并移动它的过程。

  • X先生的FU只能移动到与其当前所在方格相邻的方格。
  • Y 的FU只能移动到与其当前所在方格相邻的方格。
  • 我自己的FU将其放置在与FU相同的方格上,对手的 采取FU拿

在这个游戏中,你不能连续两次超过你的回合或进入你的回合。FU无法移动。对手的 拿走所有FU的玩家获胜。


沼君观看了先生之间的比赛。幸运的是,比赛刚刚开始,双方选手 由于您还没有采取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