题目描述

$N$ 行 $N$ 列のグリッドがあり、各マスには白い駒が $1$ 個置かれているか、黒い駒が $1$ 個置かれているか、何も置かれていないかのいずれかです。
上から $i$ 行目、左から $j$ 列目のマスの状態は $S_{i,j}$ で表され、W のとき白い駒が置かれていて、B のとき黒い駒が置かれていて、. のときは何も置かれていない空マスです。

高橋君とすぬけ君がゲームをします。高橋君からはじめて、交互にターンが回ってきます。

高橋君のターンには、

• $1$ つ上に空マスがあるような白い駒を $1$ つ選び、上に進める
• 好きな黒い駒を $1$ つ食べる

のいずれかの操作をします。

すぬけ君のターンには、

• $1$ つ上に空マスがあるような黒い駒を $1$ つ選び、上に進める
• 好きな白い駒を $1$ つ食べる

のいずれかの操作をします。

操作ができなくなった方が負けとします。両者が最適に行動するとき、どちらが勝ちますか？

なお「駒を上に進める」とは、$i$ 行 $j$ 列目の駒を $i-1$ 行 $j$ 列目に移動させることを指します。
高橋君とすぬけ君は同じ向きから盤面を見ていて、「上」というのは両者にとって同じ向きであることに注意してください。

输入格式

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

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

输出格式

高橋君が勝つならば Takahashi と、すぬけ君が勝つならば Snuke と出力せよ。

题目大意

给定一个 $n\times n$ 的棋盘, 每个格子上有一个黑棋或一个白棋或什么也没有, 两人轮流进行操作, 无法进行操作的人输.

先手每次可以进行以下两种操作之一

1. 选一个可以向上移动的白棋, 将其上移一格.

2. 吃掉一个黑棋.

后手每次可以进行以下两种操作之一

1. 选一个可以向上移动的黑棋, 将其上移一格.

2. 吃掉一个白棋.

不能将棋子移出棋盘.

加入两人均走最优策略, 问最终胜者是谁.

(两人看棋盘的方向相同)

3
BB.
.B.
...

Takahashi

2
..
WW

Snuke

4
WWBW
WWWW
BWB.
BBBB

Snuke

提示

制約

• $1\ \leq\ N\ \leq\ 8$
• $N$ は整数
• $S_{i,j}$ は W または B または . である

Sample Explanation 1

はじめに高橋君が $1$ 行 $1$ 列目の黒い駒を食べると、盤面は下のようになります。 .B. .B. ... このときすぬけ君は操作を行うことができないので、高橋君の勝ちです。 盤面の外に駒を動かすことや、他の駒があるマスに駒を移動させることはできないことに注意してください。