AT_code_festival_2015_okinawa_c Cat versus Wolf

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-okinawa-open/tasks/code_festival_2015_okinawa_c 猫 Snuke 和狼 Sothe 正在玩一种游戏来庆祝新年。有 $N$ 层设计好的积木，在积木的最顶端有一个达摩娃娃（日本传统装饰品）。两名玩家轮流依次移除一个积木，并保持达摩娃娃依然在最顶端。 下图展示了一个积木的例子、从底部数奇数层的积木的平面图，以及从底部数偶数层的积木的平面图。  猫 Snuke 先手，然后两人轮流从剩余的积木中每次移除一个积木。然而，如果移除某个积木会导致剩下的积木**变得不稳定**，则不允许移除该积木。其他积木都可以被移除。如果只剩下不能被移除的积木，则轮到的玩家输掉游戏。 **不稳定的摆放**定义如下：在 $N$ 层积木中，存在一层没有积木，或者仅在该层的某一端只剩下一个积木。 将给出游戏进行中的状态。由于猫 Snuke 先手，如果已经被移除的积木数量为偶数，则下一回合轮到猫 Snuke；否则，轮到狼 Sothe。请判断如果两人都采取最优策略，最终哪位玩家会获胜。

输入将通过标准输入给出，格式如下： > $N$ > $c_{1,1,1} c_{1,1,2} c_{1,1,3}$ > $c_{1,2,1} c_{1,2,2} c_{1,2,3}$ > $c_{1,3,1} c_{1,3,2} c_{1,3,3}$ > $c_{2,1,1} c_{2,1,2} c_{2,1,3}$ > $c_{2,2,1} c_{2,2,2} c_{2,2,3}$ > $c_{2,3,1} c_{2,3,2} c_{2,3,3}$ > ... > $c_{N,1,1} c_{N,1,2} c_{N,1,3}$ > $c_{N,2,1} c_{N,2,2} c_{N,2,3}$ > $c_{N,3,1} c_{N,3,2} c_{N,3,3}$ - 第一行给出一个整数 $N$，$1 \leq N \leq 50,000$。 - 接下来的 $3N$ 行描述当前游戏状态。从第 $3i-2$ 行到第 $3i$ 行，给出第 $i$ 层（从底部数起）的信息。在第 $3(i-1)+j$ 行（$1 \leq i \leq N, 1 \leq j \leq 3$），给出 $c_{i,j,1}$、$c_{i,j,2}$、$c_{i,j,3}$，它们之间没有分隔符。每个字符为 `#` 或 `.`。如果 $c_{i,j,k}$ 为 `#`，表示第 $i$ 层对应位置的积木尚未被移除；如果为 `.`，表示该位置的积木已被移除。 - 如果 $i$ 为奇数，则对于 $k=1,2,3$，有 $c_{i,1,k}=c_{i,2,k}=c_{i,3,k}$。 - 如果 $i$ 为偶数，则对于 $j=1,2,3$，有 $c_{i,j,1}=c_{i,j,2}=c_{i,j,3}$。  左图为从底部数奇数层的积木平面图，右图为从底部数偶数层的积木平面图。 输入保证当前状态不是**不稳定的摆放**。

请判断如果两位玩家都采取最优策略，最终哪位玩家会获胜。如果猫 Snuke 获胜，输出一行 `Snuke`；否则，如果狼 Sothe 获胜，输出一行 `Sothe`。 输出末尾需换行。

### 题目说明 猫 Snuke 和狼 Sothe 轮流移除积木，保持达摩娃娃在顶端。每次只能移除不会导致**不稳定摆放**的积木。若轮到某位玩家时已无可移除的积木，则该玩家输掉游戏。 **不稳定摆放**：在 $N$ 层积木中，存在一层没有积木，或仅在该层的某一端只剩下一个积木。 输入给出当前状态。猫 Snuke 先手，如果已被移除的积木数为偶数，则下一回合轮到猫 Snuke，否则轮到狼 Sothe。请判断最终哪位玩家会获胜。 ### 样例解释 1 如果猫 Snuke 移除第 2 层（从底部数起）尚未被移除的端点积木，狼 Sothe 将无可移除的积木。 ### 样例解释 3 注意输入状态下已有 3 个积木被移除，因此下一回合轮到狼 Sothe。 由 ChatGPT 4.1 翻译