C2. Ренака Амаори и XOR-игра (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между легкой и сложной версиями заключается в том, что в сложной версии $$$a_i, b_i \leq 10^6$$$.

Ренака застряла между молотом и наковальней... и под этим, конечно, я имею в виду Адзисай и Маи! Обе они хотят проводить с ней время, а она просто не может решить, с кем! Поэтому Адзисай и Маи решили сыграть в XOR-игру.

Адзисай и Маи даны массивы $$$a$$$ и $$$b$$$ длины $$$n$$$ ($$$0\leq a_i, b_i\leq {\color{red}{10^6}}$$$). Они будут играть в игру, которая длится $$$n$$$ ходов, где Адзисай ходит на нечетных ходах, а Маи на четных. На $$$i$$$-м ходу игрок, который ходит, может выбрать, поменять местами $$$a_i$$$ с $$$b_i$$$, или пропустить ход.

Обратите внимание, что если происходит обмен, индекс, который меняется местами, должен совпадать с номером хода. Например, на первом ходе Адзисай может выбрать поменять местами $$$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$$$ обозначает побитовую операцию XOR

Входные данные

Первая строка содержит одно целое число $$$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 10^6$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$b_1, b_2, \dots, b_n$$$ ($$$0\leq b_i\leq 10^6$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке «Ajisai», если Адзисай выигрывает при оптимальной игре, «Mai», если Маи выигрывает при оптимальной игре, или «Tie», если игра заканчивается вничью при оптимальной игре.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «mAi», «mai», «MAI», и «maI» будут распознаны как «Mai».

Пример
Входные данные
6
4
1 4 6 1
3 2 3 7
6
20 11 1 7 7 0
14 8 3 6 17 6
4
2 6 3 6
3 4 7 1
5
1 4 5 5 3
6 7 1 2 13
6
9 5 9 17 17 6
1 13 6 13 1 15
5
2 3 8 1 5
3 1 6 14 7
Выходные данные
Mai
Ajisai
Tie
Ajisai
Mai
Tie
Примечание

В первом примере один из возможных исходов игры может быть следующим:

На первом ходе Адзисай выбирает поменять местами $$$a_1$$$ и $$$b_1$$$. Теперь массивы: $$$a = [3, 4, 6, 1]$$$ и $$$b = [1, 2, 3, 7]$$$.

На втором ходе Маи выбирает поменять местами $$$a_2$$$ и $$$b_2$$$. Теперь массивы: $$$a = [3, 2, 6, 1]$$$ и $$$b = [1, 4, 3, 7]$$$.

На третьем ходе Адзисай выбирает пропустить ход.

На четвертом ходе Маи выбирает поменять местами $$$a_4$$$ и $$$b_4$$$. Теперь массивы: $$$a = [3, 2, 6, 7]$$$ и $$$b = [1, 4, 3, 1]$$$.

Теперь финальный счет Адзисай равен $$$3\oplus 2\oplus 6\oplus 7 = 0$$$, а финальный счет Маи равен $$$1\oplus 4\oplus 3\oplus 1 = 7$$$. Поэтому Маи выигрывает игру.

Не гарантируется, что вышеуказанное описание является представительным для оптимальной игры.

Для дополнительных примеров смотрите примеры легкой версии.