前进或吃掉

题目描述

有一个 $N$ 行 $N$ 列的网格,每个格子中可能放有 1 个白色棋子、1 个黑色棋子,或什么都没有。

从上数第 $i$ 行、从左数第 $j$ 列的格子状态用 $S_{i,j}$ 表示:若 $S_{i,j}$ 为 W,则该格子有白色棋子;若为 B,则有黑色棋子;若为 .,则为空。

高桥君和 Snuke 进行游戏,高桥君先手,两人轮流行动。

高桥君每回合执行以下操作之一:

• 选择 1 个上方一格为空格的白色棋子,将其向上移动 1 格(见下文)。
• 吃掉 1 个自己选择的黑色棋子。

Snuke 每回合执行以下操作之一:

• 选择 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 获胜,输出 Snuke。

样例

3
BB.
.B.
...

Takahashi

如果高桥君吃掉第 $1$ 行第 $1$ 列的黑色棋子,盘面将变为:

.B.
.B.
...

此时 Snuke 无法执行任何操作,因此高桥君获胜。

注意不允许将棋子移动到棋盘外,或移动到有其他棋子的格子。

2
..
WW

Snuke

4
WWBW
WWWW
BWB.
BBBB

Snuke

数据范围

• $1 \leq N \leq 8$
• $N$ 是整数
• $S_{i,j}$ 为 W、B 或 .