102297: [AtCoder]ABC229 H - Advance or Eat

Problem Statement

There is a grid with $N$ rows and $N$ columns, where each square has one white piece, one black piece, or nothing on it.
The square at the $i$-th row from the top and $j$-th column from the left is described by $S_{i,j}$. If $S_{i,j}$ is W, the square has a white piece; if $S_{i,j}$ is B, it has a black piece; if $S_{i,j}$ is ., it is empty.

Takahashi and Snuke will play a game, where the players take alternate turns, with Takahashi going first.

In Takahashi's turn, he does one of the following operations.

• Choose a white piece that can move one square up to an empty square, and move it one square up (see below).
• Eat a black piece of his choice.

In Snuke's turn, he does one of the following operations.

• Choose a black piece that can move one square up to an empty square, and move it one square up.
• Eat a white piece of his choice.

The player who becomes unable to do the operation loses the game. Which player will win when both players play optimally?

Here, moving a piece one square up means moving a piece at the $i$-th row and $j$-th column to the $(i-1)$-th row and $j$-th column.
Note that this is the same for both players; they see the board from the same direction.

Constraints

• $1 \leq N \leq 8$
• $N$ is an integer.
• $S_{i,j}$ is W, B, or ..

Input

Input is given from Standard Input in the following format:

$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}$

Output

If Takahashi will win, print Takahashi; if Snuke will win, print Snuke.

Sample Input 1

3
BB.
.B.
...

Sample Output 1

Takahashi

If Takahashi eats the black piece at the $1$-st row and $1$-st columns, the board will become:

.B.
.B.
...

Then, Snuke cannot do an operation, making Takahashi win.
Note that it is forbidden to move a piece out of the board or to a square occupied by another piece.

Sample Input 2

2
..
WW

Sample Output 2

Snuke

Sample Input 3

4
WWBW
WWWW
BWB.
BBBB

Sample Output 3

Snuke

问题描述

有一个包含$N$行和$N$列的网格，每个方块上有一个白色棋子、一个黑色棋子或什么都没有。
从顶部数第$i$行，从左数第$j$列的方块由$S_{i,j}$描述。如果$S_{i,j}$是W，则该方块上有一个白色棋子；如果$S_{i,j}$是B，则该方块上有一个黑色棋子；如果$S_{i,j}$是.，则该方块为空。

高桥和スネーク将进行一场比赛，玩家轮流行动，高桥先走。

在高桥的回合中，他会执行以下操作之一。

• 选择一个可以向上移动一个空格的白色棋子，并将其向上移动一个空格（见下文）。
• 吃掉一个他选择的黑色棋子。

在スネーク的回合中，他会执行以下操作之一。

• 选择一个可以向上移动一个空格的黑色棋子，并将其向上移动一个空格。
• 吃掉一个他选择的白色棋子。

当玩家无法执行操作时，该玩家输掉比赛。当两个玩家都发挥出最佳水平时，哪位玩家会赢？

在这里，将棋子向上移动一个空格意味着将位于第$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。

样例输入 1

3
BB.
.B.
...

样例输出 1

Takahashi

如果高桥吃掉位于第$1$行和第$1$列的黑色棋子，棋盘将变为：

.B.
.B.
...

然后，スネーク无法执行操作，使高桥获胜。
请注意，禁止将棋子移出棋盘或移至另一个棋子所在的方块。

样例输入 2

2
..
WW

样例输出 2

Snuke

样例输入 3

4
WWBW
WWWW
BWB.
BBBB

样例输出 3

Snuke