题目描述

是的。我再也受不了了。绝对不行。

——天织恋奏

这是该问题的困难版本。困难版本与简单版本的唯一区别是本题中 $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$ 表示按位异或运算。

输入格式

第一行包含一个整数 $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”。

样例

6
4
1 4 6 1
3 2 3 7
6
20 11 1 7 7 0
14 8 3 6 17 6
4
2 6 3 6
3 4 7 1
5
1 4 5 5 3
6 7 1 2 13
6
9 5 9 17 17 6
1 13 6 13 1 15
5
2 3 8 1 5
3 1 6 14 7

Mai
Ajisai
Tie
Ajisai
Mai
Tie

样例说明

在第一个样例中，游戏流程可能如下：

第 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 翻译

来源

Codeforces 2171C2，英文题名 Renako Amaori and XOR Game (hard version)。