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

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

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

Адзисай и Маи даны массивы $$$a$$$ и $$$b$$$ длины $$$n$$$ ($$$0\leq a_i, b_i\leq {\color{red}{1}}$$$). Они будут играть в игру, которая длится $$$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 1$$$).

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

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

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

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

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

Пример
Входные данные
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
Выходные данные
Ajisai
Mai
Tie
Ajisai
Tie
Mai
Примечание

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

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

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

На третьем ходе Адзисай выбирает поменять местами $$$a_3$$$ и $$$b_3$$$. Теперь массивы: $$$a = [1, 0, 1, 1]$$$ и $$$b = [1, 0, 0, 1]$$$.

На четвертом ходе Маи выбирает поменять местами $$$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$$$. Таким образом, Адзисай выигрывает игру.

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