CF2171C2 Renako Amaori and XOR Game (hard version)

Yup. I couldn't do this any longer. No. Freaking. Way. — Renako Amaori This is the hard version of the problem. The only difference between the easy and hard versions is that in the hard version, $ a_i, b_i \leq 10^6 $ . 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}{10^6}} $ ). 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](https://en.wikipedia.org/wiki/Bitwise_operation#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 10^6 $ ). The third line of each test case contains $ n $ integers, $ b_1, b_2, \dots, b_n $ ( $ 0\leq b_i\leq 10^6 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 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".

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 = [3, 4, 6, 1] $ and $ b = [1, 2, 3, 7] $ . On turn 2, Mai chooses to swap $ a_2 $ and $ b_2 $ . Now the arrays are $ a = [3, 2, 6, 1] $ and $ b = [1, 4, 3, 7] $ . On turn 3, Ajisai chooses to pass. On turn 4, Mai chooses to swap $ a_4 $ and $ b_4 $ . Now the arrays are $ a = [3, 2, 6, 7] $ and $ b = [1, 4, 3, 1] $ . Now, Ajisai's final score is $ 3\oplus 2\oplus 6\oplus 7 = 0 $ and Mai's final score is $ 1\oplus 4\oplus 3\oplus 1 = 7 $ . Therefore, Mai wins the game. It is not guaranteed that the above description is representative of optimal play. For additional examples, see the examples of the easy version.