Renako Amaori and XOR Game (easy version)

Because $a_i,b_i\le 1$, this game looks way more complicated than it is. There are $n$ turns, swaps, optimal play, anime emotional damage, etc. But the whole thing collapses into parity.

Let Ajisai's final XOR be $A$, and Mai's final XOR be $B$.

Equal positions are boring

If $a_i=b_i$, then swapping does nothing. The pair is either $(0,0)$ or $(1,1)$, so both players receive the same contribution from that index.

These indices may flip both final XORs, but they never create an advantage for either player.

So the only interesting positions are the mismatches:

$a_i\ne b_i.$

At such an index, the pair is either $(0,1)$ or $(1,0)$. Whoever controls that turn can choose whether Ajisai gets $0$ or $1$ from this position. Mai gets the opposite bit.

Track only the mismatches

Suppose there are $m$ mismatching indices.

For each mismatching index, let $x_i$ be the final bit contributed to Ajisai's XOR. Since the pair contains one $0$ and one $1$, the bit contributed to Mai is:

$1-x_i = x_i\oplus 1.$

Let $E$ be the XOR contribution from all equal positions. Equal positions contribute the same thing to both players.

Then:

$A = E \oplus x_1 \oplus x_2 \oplus \cdots \oplus x_m$

and

$B = E \oplus (x_1\oplus 1) \oplus (x_2\oplus 1) \oplus \cdots \oplus (x_m\oplus 1).$

XORing $1$ exactly $m$ times adds $m\bmod 2$, so:

$B = A \oplus (m\bmod 2).$

That one equation is basically the whole problem.

Case 1: $m$ is even

Then:

$B=A.$

The scores are always equal, regardless of what anyone does. Neither player can force a win because a win is impossible.

So the answer is:

$\text{Tie}.$

Case 2: $m$ is odd

Then:

$B=A\oplus 1.$

So the final scores are always opposite. There cannot be a tie.

Ajisai wins exactly when $A=1$. Mai wins exactly when $A=0$.

Now we only need to know who can force the final value of $A$.

Every mismatching index lets its controller choose whether Ajisai receives $0$ or $1$ from that index. Since the final score depends only on XOR parity, the last mismatching index is decisive.

Why? By the time that turn happens, all earlier useful choices are fixed. The player moving at the last mismatch sees the current parity and can choose the final bit at this index to make $A$ whatever they want.

• If the last mismatching index is odd, Ajisai controls it and can force $A=1$.
• If the last mismatching index is even, Mai controls it and can force $A=0$.

That's it. No giant minimax tree needed. The last useful move owns the parity button.

Algorithm

For each test case:

1. Count how many indices satisfy $a_i\ne b_i$.
2. Store the last such index.
3. If the count is even, print Tie.
4. Otherwise, if the last mismatching index is odd in 1-based indexing, print Ajisai.
5. Otherwise, print Mai.

Complexity

We scan the arrays once.

$O(n)$ per test case, with total $O(\sum n)$ over all test cases.

Memory usage is $O(n)$ here because we store the arrays, though it could also be done with $O(n)$ input storage as written comfortably under the limits.