CF2171C1.Renako Amaori and XOR Game (easy version)

Yup. I couldn't do this any longer. No. Freaking. Way.

— Renako Amaori

This is the easy version of the problem. The only difference between the easy and hard versions is that in the easy version, $a_i, b_i \leq 1$.

Renako is stuck between a rock and a hard place... and by that, of course, I mean Ajisai and Mai! Both of them want to hang out with her, and she just can't decide! So Ajisai and Mai have decided to play the XOR game.

Ajisai and Mai are given arrays $a$ and $b$ of length $n$ ($0\leq a_i, b_i\leq {\color{red}{1}}$). They will play a game that lasts for $n$ turns, where Ajisai moves on odd-numbered turns and Mai moves on even-numbered turns. On the $i$-th turn, the player to move may choose to swap $a_i$ and $b_i$, or pass.

Note that if a swap occurs, the index that is being swapped must match the turn number. For example, on the first turn, Ajisai may choose to swap $a_1$ and $b_1$, or pass. On the second turn, Mai may choose to swap $a_2$ and $b_2$, or pass. This continues for $n$ turns. Thus, only Ajisai can swap odd indices, and only Mai can swap even indices.

At the end of the game, Ajisai achieves a score of $a_1 \oplus a_2 \oplus \dots \oplus a_n$, and Mai achieves a score of $b_1 \oplus b_2 \oplus \dots \oplus b_n$$^{\text{∗}}$. The player with the higher score wins. If the players have the same score, the game ends in a tie.

Determine the outcome of the game with optimal play. More formally, one player is considered to win with optimal play if there exists a strategy for them such that they always win, regardless of their opponent's choices. The game is considered a tie with optimal play if neither player has such a strategy.

$^{\text{∗}}$$\oplus$ denotes the bitwise XOR operation

是的，我再也受不了了。不。 freaking。 行。

——天ori 莲子

本题为简单版本。简单版本与困难版本的唯一区别在于：在简单版本中，$a_i, b_i \leq 1$。

莲子正陷入两难境地……当然，我指的就是紫阳花和舞！她们俩都想和莲子一起玩，而莲子却难以抉择！于是，紫阳花和舞决定玩一个异或（XOR）游戏。

紫阳花和舞分别获得长度为 $n$ 的数组 $a$ 和 $b$（其中 $0\leq a_i, b_i\leq {\color{red}{1}}$）。她们将进行一场持续 $n$ 回合的游戏：紫阳花在奇数回合行动，舞在偶数回合行动。在第 $i$ 回合，当前行动的玩家可选择交换 $a_i$ 与 $b_i$，或选择跳过（pass）。

注意：若发生交换，则被交换元素的下标必须与当前回合编号一致。例如，在第一回合，紫阳花可选择交换 $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$$^{\text{∗}}$。得分更高的玩家获胜；若双方得分相同，则游戏以平局结束。

请判断在双方均采用最优策略的情况下，游戏的最终结果。更准确地说：若存在某位玩家的一种策略，使得无论对手如何应对，该玩家均必胜，则称该玩家在最优策略下获胜；若双方均不存在这样的必胜策略，则称游戏在最优策略下以平局结束。

$^{\text{∗}}$$\oplus$ 表示 按位异或运算（bitwise XOR）

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\leq n\leq 2\cdot 10^5$).

The second line of each test case contains $n$ integers, $a_1, a_2, \dots, a_n$ ($0\leq a_i\leq 1$).

The third line of each test case contains $n$ integers, $b_1, b_2, \dots, b_n$ ($0\leq b_i\leq 1$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output on a single line "Ajisai" if Ajisai wins with optimal play, "Mai" if Mai wins with optimal play, or "Tie" if the game ends in a tie with optimal play.

You may output the answer in any case (upper or lower). For example, the strings "mAi", "mai", "MAI", and "maI" will be recognized as "Mai".

对于每个测试用例，如果在双方都采取最优策略的情况下紫阳花获胜，则在一行中输出 “Ajisai”；如果在双方都采取最优策略的情况下舞获胜，则输出 “Mai”；如果在双方都采取最优策略的情况下游戏以平局结束，则输出 “Tie”。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “mAi”、“mai”、“MAI” 和 “maI” 均会被识别为 “Mai”。

In the first example, one way the game might play out is as follows:

On turn 1, Ajisai chooses to swap $a_1$ and $b_1$. Now the arrays are $a = [1, 0, 0, 1]$ and $b = [1, 0, 1, 1]$.

On turn 2, Mai chooses to pass.

On turn 3, Ajisai chooses to swap $a_3$ and $b_3$. Now the arrays are $a = [1, 0, 1, 1]$ and $b = [1, 0, 0, 1]$.

On turn 4, Mai chooses to swap $a_4$ and $b_4$. Now the arrays are $a = [1, 0, 1, 1]$ and $b = [1, 0, 0, 1]$.

Now, Ajisai's final score is $1\oplus 0\oplus 1\oplus 1 = 1$ and Mai's final score is $1\oplus 0\oplus 0\oplus 1 = 0$. Therefore, Ajisai wins the game.

It is not guaranteed that the above description is representative of optimal play.

在第一个例子中，游戏的一种可能进行方式如下：

第 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$。因此，阿紫赢得本局游戏。

以上描述未必代表双方的最优策略。