你和一位鸟类学家朋友在湿地观鸟,等待拍摄一种稀有鸟类。
为了打发时间,你们发明了一个小游戏。湿地由一个 $N \times N$ 的网格表示,包含三种类型的方格:坚硬地面(firm ground)、湿地区域(wet zone)和保护区域(protected zone)。
相连的湿地区域方格构成“湿地区块”(wet areas),即湿地区域方格的极大集合,使得我们可以通过相连的湿地区域方格路径从该区域的任意方格到达该区域的任何其他方格。两个方格在共享一条边时被认为是相连的,因此网格边界上的方格与 4 个其他方格相连。每个湿地区块必须同时与网格的左侧和右侧相连,且包含的湿地区域方格不超过 $2N$ 个。属于两个不同湿地区块的两个湿地区域方格之间的距离至少为 3(距离定义为在网格上水平或垂直移动的步数)。例如,在下方的两个示例中,蓝色方格之间的距离为 3。
你和你的朋友轮流在湿地上放置相机,需遵循以下限制: 相机必须放置在坚硬地面方格上。 相机必须与一个湿地区域方格相邻,以便拍摄鸟类照片。 相机不能放置在保护区域方格上。 同一个方格上不能放置两台相机。 * 任何两台与同一个湿地区块相邻的相机不能相邻(同样,相邻的定义为共享一条边)。
第一个无法放置相机的人输掉游戏。假设双方都采取最优策略,请问先手玩家会赢还是输?
输入格式
输入包含以下行: 第一行包含整数 $N$; 接下来的 $N$ 行,每行一个字符串表示网格的一行:“*”表示湿地区域方格,“.”表示坚硬地面方格,“x”表示保护区域方格。
数据范围
输入满足 $1 \le N \le 10$。
输出格式
如果先手玩家在双方最优策略下获胜,输出“First player will win”,否则输出“Second player will win”。
样例
样例输入 1
3 ... ... ***
样例输出 1
First player will win
说明 1
先手玩家可以在三个可能的位置放置相机:如果他将相机放在左侧或右侧位置,那么第二位玩家可以在另一个位置放置相机并赢得游戏。另一方面,如果先手玩家将相机放在中间,第二位玩家将无法再放置相机并输掉游戏。
样例输入 2
10 ********** *.x.*..... *...*..... *****..... .......... .......... xx******.. ***x...*.. ..*...x*.x ..********
样例输出 2
Second player will win