题目描述

没错。我再也受不了了。绝对不行。

—— 天织恋

这是该问题的简单版本。简单版本与困难版本的唯一区别是本题中 $a_i, b_i \leq 1$。

天织恋陷入了进退两难的境地……当然，这指的是紫阳和舞！她们都想和她一起玩，而她实在难以抉择！所以紫阳和舞决定玩异或游戏。

紫阳和舞分别得到长度为 $n$ 的数组 $a$ 和 $b$（$0 \leq a_i, b_i \leq {\color{red}{1}}$）。她们将进行一个持续 $n$ 回合的游戏，紫阳在奇数回合操作，舞在偶数回合操作。在第 $i$ 回合，当前轮到操作的玩家可以选择交换 $a_i$ 和 $b_i$，也可以选择跳过。

注意，如果选择交换，则交换的位置必须和当前回合数相同。例如，在第 $1$ 回合时，紫阳可以选择交换 $a_1$ 和 $b_1$，或者选择不操作。在第 $2$ 回合时，舞可以选择交换 $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$。分数更高的玩家获胜。如果二人分数相同，则为平局。

请你判断在最优策略下，这场游戏的结果。如果某位玩家存在一种策略，无论对方如何操作，都必胜，则她在最优博弈下胜出。如果双方都无法必胜，则为平局。

$^\text{∗}$ 这里 $\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 1$）。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \leq b_i \leq 1$）。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行，内容可为 "Ajisai"（若紫阳最优策略必胜）、"Mai"（若舞最优策略必胜）、"Tie"（若双方最优策略下为平局）。

输出时不区分大小写，例如 "mAi"、"mai"、"MAI"、"maI" 都将被视为 "Mai"。

样例

6
4
1 0 0 1
1 0 1 1
6
0 1 1 1 1 0
0 0 1 0 1 1
4
0 0 1 0
1 0 1 1
5
1 0 1 1 1
0 1 1 1 0
6
1 1 1 1 1 1
1 1 1 1 1 1
5
0 1 0 0 1
1 0 0 1 1

Ajisai
Mai
Tie
Ajisai
Tie
Mai

样例说明

在第一个样例中，可能的一轮操作如下：

第 $1$ 回合，紫阳选择交换 $a_1$ 和 $b_1$。此时数组 $a = [1, 0, 0, 1]$，$b = [1, 0, 1, 1]$。

第 $2$ 回合，舞选择跳过操作。

第 $3$ 回合，紫阳选择交换 $a_3$ 和 $b_3$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。

第 $4$ 回合，舞选择交换 $a_4$ 和 $b_4$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。

最终，紫阳的得分为 $1 \oplus 0 \oplus 1 \oplus 1 = 1$，舞的得分为 $1 \oplus 0 \oplus 0 \oplus 1 = 0$，因此紫阳获胜。

注意，上述操作不是一定符合最优策略。

由 ChatGPT 5 翻译

来源

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