这是问题的困难版本。简单版本和困难版本之间的唯一区别在于,在困难版本中,$$$a_i, b_i \leq 10^6$$$。
Renako 陷入进退两难的境地......当然,我指的是 Ajisai 和 Mai!两个人都想和她一起出去玩,她就是拿不定主意!因此,Ajisai 和 Mai 决定玩 XOR 游戏。
Ajisai 和 Mai 被赋予长度 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$ ($$$0\leq a_i, b_i\leq {\color{red}{10^6}}$$$)。他们将玩一场持续 $$$n$$$ 回合的游戏,其中 Ajisai 在奇数回合中移动,Mai 在偶数回合中移动。在第 $$$i$$$ 回合,要移动的玩家可以选择交换 $$$a_i$$$ 和 $$$b_i$$$,或者放弃。
请注意,如果发生交换, 正在交换的索引必须与回合数匹配。例如,在第一回合,Ajisai 可以选择交换 $$$a_1$$$ 和 $$$b_1$$$,或者通过。在第二回合,Mai 可以选择交换 $$$a_2$$$ 和 $$$b_2$$$,或者通过。这将持续 $$$n$$$ 回合。因此,只有 Ajisai 可以交换奇数索引,只有 Mai 可以交换偶数索引。
游戏结束时,Ajisai 的得分为 $$$a_1 \oplus a_2 \oplus \dots \oplus a_n$$$,Mai 的得分为 $$$b_1 \oplus b_2 \oplus \dots \oplus b_n$$$$$$^{\text{*}}$$$。得分较高的玩家获胜。如果双方得分相同,则比赛以平局结束。
以最佳发挥确定游戏结果。更正式地说,如果存在一种策略,使一名玩家无论对手的选择如何总是获胜,则认为他以最佳发挥获胜。如果双方都没有这样的策略,则该游戏被视为具有最佳玩法的平局。
$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 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\cdot 10^5$$$。
输出
对于每个测试用例,在单行上输出“紫菜斋“如果Ajisai以最佳发挥获胜,”麦“如果Mai以最佳发挥获胜,或者”领带“如果比赛以最佳发挥平局结束。
您可以在任何情况下输出答案(上限或下限)。例如,字符串“毫安", "麦", "麦“,和”邮件“将被识别为”麦".
示例
输入复制
641 4 6 13 2 3 7620 11 1 7 7 014 8 3 6 17 642 6 3 63 4 7 151 4 5 5 36 7 1 2 1369 5 9 17 17 61 13 6 13 1 1552 3 8 1 53 1 6 14 7
输出复制
MaiAjisaiTieAjisaiMaiTie
注意
在第一个示例中,游戏可能的一种玩法如下:
在第 1 回合,Ajisai 选择交换 $$$a_1$$$ 和 $$$b_1$$$。现在数组是 $$$a = [3, 4, 6, 1]$$$ 和 $$$b = [1, 2, 3, 7]$$$。
在第 2 回合,Mai 选择交换 $$$a_2$$$ 和 $$$b_2$$$。现在数组是 $$$a = [3, 2, 6, 1]$$$ 和 $$$b = [1, 4, 3, 7]$$$。
在第3回合,Ajisai选择放弃。
在第 4 回合,Mai 选择交换 $$$a_4$$$ 和 $$$b_4$$$。现在数组是 $$$a = [3, 2, 6, 7]$$$ 和 $$$b = [1, 4, 3, 1]$$$。
现在,Ajisai 的最终得分为 $$$3\oplus 2\oplus 6\oplus 7 = 0$$$,Mai 的最终得分为 $$$1\oplus 4\oplus 3\oplus 1 = 7$$$。因此,麦赢得了比赛。
不保证上述描述代表最佳播放。
有关其他示例,请参阅简单版本的示例。