配点 : $600$ 点

問題文

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

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

高橋君のターンには、

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

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

すぬけ君のターンには、

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

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

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

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

制約

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

入力

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

$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 と出力せよ。

3
BB.
.B.
...

Takahashi

はじめに高橋君が $1$ 行 $1$ 列目の黒い駒を食べると、盤面は下のようになります。

.B.
.B.
...

このときすぬけ君は操作を行うことができないので、高橋君の勝ちです。 盤面の外に駒を動かすことや、他の駒があるマスに駒を移動させることはできないことに注意してください。

2
..
WW

Snuke

4
WWBW
WWWW
BWB.
BBBB

Snuke