CF2171C2 Renako Amaori and XOR Game (hard version)

是的。我再也受不了了。绝对不行。 ——天织恋奏 这是该问题的困难版本。困难版本与简单版本的唯一区别是本题中 $a_i, b_i \leq 10^6$。 天织恋奏陷入了两难的境地……当然，这里指的是紫阳花和春日！她们都想和恋奏一起玩，而恋奏却不知道如何选择！于是，紫阳花和春日决定来进行 XOR 游戏。 紫阳花和春日分别得到了长度为 $n$ 的数组 $a$ 和 $b$（$0\leq a_i, b_i\leq 10^6$）。她们将玩一个持续 $n$ 回合的游戏，其中紫阳花在奇数回合行动，春日在偶数回合行动。在第 $i$ 回合，当前回合的玩家可以选择交换 $a_i$ 与 $b_i$，或者选择不交换。 注意，若发生交换，被交换的下标必须和当前回合编号一致。例如，在第一回合，紫阳花可以选择交换 $a_1$ 和 $b_1$，或选择跳过。在第二回合，春日可以选择交换 $a_2$ 和 $b_2$，或选择跳过。如此循环，直到第 $n$ 回合。也就是说，紫阳花只能操作奇数下标，春日只能操作偶数下标。 游戏结束后，紫阳花的得分为 $a_1 \oplus a_2 \oplus \dots \oplus a_n$，春日的得分为 $b_1 \oplus b_2 \oplus \dots \oplus b_n$。得分更高的玩家获胜。如果两人得分相同，则为平局。 请判断在双方都采取最优策略的情况下，游戏的结果。更具体地说，若某一方总有办法无论对方作何决策都能获胜，那么认为她以最优策略获胜；若双方都无法保证必胜，则认为游戏以平局结束。 $^{\ast}$ 这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例个数。 每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 2\times 10^5$）。 第二行包含 $n$ 个整数，表示 $a_1, a_2, \dots, a_n$（$0\leq a_i\leq 10^6$）。 第三行包含 $n$ 个整数，表示 $b_1, b_2, \dots, b_n$（$0\leq b_i\leq 10^6$）。 保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

对于每个测试用例，输出一行，若紫阳花能以最优策略获胜则输出 "Ajisai"，若春日能以最优策略获胜则输出 "Mai"，若游戏以平局结束则输出 "Tie"。 答案不区分大小写。例如，“mAi”、“mai”、“MAI”、“maI”都被识别为“Mai”。

在第一个样例中，游戏流程可能如下： 第 1 回合，紫阳花选择交换 $a_1$ 与 $b_1$。此时数组变为 $a=[3, 4, 6, 1]$，$b=[1, 2, 3, 7]$。 第 2 回合，春日选择交换 $a_2$ 与 $b_2$。此时数组变为 $a=[3, 2, 6, 1]$，$b=[1, 4, 3, 7]$。 第 3 回合，紫阳花选择跳过。 第 4 回合，春日选择交换 $a_4$ 与 $b_4$。此时数组变为 $a=[3, 2, 6, 7]$，$b=[1, 4, 3, 1]$。 最终紫阳花得分为 $3\oplus 2\oplus 6\oplus 7 = 0$，春日得分为 $1\oplus 4\oplus 3\oplus 1 = 7$，因此春日获胜。 上述描述未必是最优策略的结果。 更多样例请参考简单版本的示例。 由 ChatGPT 5 翻译