CFCF2171C1.Renako Amaori and XOR Game (easy version)

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

—— 天织恋

这是该问题的简单版本。简单版本与困难版本的唯一区别是本题中 $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"。

输入输出样例

输入#1

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

输出#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$ ，因此紫阳获胜。

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

首页