A16553 | 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”。