小猫钓鱼

Problem Description

shuishui 和 sha7dow 在玩 小猫钓鱼。 游戏规则如下：

• 游戏开始时，shuishui 和 sha7dow 各有 $n$ 张牌，每张牌上标有 $[1,n]$ 中的一个整数，且 $[1,n]$ 中每个整数各出现 $2$ 次；
• shuishui 初始牌为 $a:a_1,a_2,...,a_n$，sha7dow 初始牌为 $b:b_1,b_2,...,b_n$；
• 游戏开始后，两人轮流操作，将手中的任意一张牌置于牌堆顶部（牌堆初始为空）。假设放置的牌的点数为 $x$，若放置前牌堆中已存在点数为 $x$ 的牌，则放置该牌的玩家 从牌堆顶往下，直到牌堆中原有的点数为 $x$ 的牌，将这些牌全部拿走，放入己方手牌中（包括 放置的点数为 $x$ 的牌 和 原有的点数为 $x$ 的牌），并获得等同于拿走牌数量的分数。
• 轮到一个玩家放置手牌时，若此时其手牌为空，则游戏结束。
• 游戏结束后，分数较高的玩家获胜，若分数相同或者游戏不会结束，则游戏没有胜者。 给定 shuishui 和 sha7dow 的初始手牌，shuishui 先手操作。假设 shuishui 和 sha7dow 足够聪明，且都以获胜为目的，请你求出游戏的胜者，或者报告游戏没有胜者。

Input

输入包含多组测试数据。 第一行包含一个整数 $T$ ($1 \leq T \leq 5000$)，表示测试数据的组数。 对于每组测试数据： 第一行包含一个整数 $n$ ($1 \leq n \leq 2 \times 10^5$)，表示初始双方的手牌数； 第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ ($1 \leq a_i \leq n$)，表示 shuishui 的初始手牌； 第三行包含 $n$ 个正整数 $b_1,b_2,\cdots,b_n$ ($1 \leq b_i \leq n$)，表示 sha7dow 的初始手牌； 输入保证在 $a$ 和 $b$ 中，$[1,n]$ 中每个数各出现 $2$ 次。 保证所有的测试数据中 $n$ 的总和不超过 $5 \times 10^5$ 。

Output

对于每组测试数据： 输出一行一个字符串： 若 shuishui 获胜，输出 shuishui； 若 sha7dow 获胜，输出 sha7dow； 若游戏没有胜者，输出 Tie 。

Sample Input

1
3
1 1 2
3 3 2

Sample Output

shuishui

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）