这是问题的简单版本。简单版本和困难版本之间的唯一区别是,在简单版本中,$$$a_i, b_i \leq 1$$$。
Renako 陷入进退两难的境地……当然,我指的是 Ajisai 和 Mai!两个人都想和她一起出去玩,她就是拿不定主意!因此,Ajisai 和 Mai 决定玩 XOR 游戏。
Ajisai 和 Mai 被赋予长度 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$ ($$$0\leq a_i, b_i\leq {\color{red}{1}}$$$)。他们将玩一场持续 $$$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 1$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数,$$$b_1, b_2, \dots, b_n$$$ ($$$0\leq b_i\leq 1$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在单行上输出“紫菜斋“如果紫斋以最佳发挥获胜,”麦“如果Mai以最佳发挥获胜,或者”领带“如果比赛以最佳发挥平局结束。
您可以在任何情况下输出答案(上限或下限)。例如,字符串“毫安", "麦", "麦“,和”邮件“将被识别为”麦".
示例
输入复制
641 0 0 11 0 1 160 1 1 1 1 00 0 1 0 1 140 0 1 01 0 1 151 0 1 1 10 1 1 1 061 1 1 1 1 11 1 1 1 1 150 1 0 0 11 0 0 1 1
输出复制
AjisaiMaiTieAjisaiTieMai
注意
在第一个示例中,游戏可能的一种玩法如下:
在第 1 回合,Ajisai 选择交换 $$$a_1$$$ 和 $$$b_1$$$。现在数组是 $$$a = [1, 0, 0, 1]$$$ 和 $$$b = [1, 0, 1, 1]$$$。
在第2回合,Mai选择放弃。
在第 3 回合,Ajisai 选择交换 $$$a_3$$$ 和 $$$b_3$$$。现在数组是 $$$a = [1, 0, 1, 1]$$$ 和 $$$b = [1, 0, 0, 1]$$$。
在第 4 回合,Mai 选择交换 $$$a_4$$$ 和 $$$b_4$$$。现在数组是 $$$a = [1, 0, 1, 1]$$$ 和 $$$b = [1, 0, 0, 1]$$$。
现在,Ajisai 的最终得分为 $$$1\oplus 0\oplus 1\oplus 1 = 1$$$,Mai 的最终得分为 $$$1\oplus 0\oplus 0\oplus 1 = 0$$$。因此,阿吉斋赢得了比赛。
不保证上述描述代表最佳播放。