Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 1024 MB 總分: 100
统计

Доктор Менджи — эксперт в области искусственного интеллекта. Сейчас он обучает Бота — AGI (Artificial Game Intelligence, искусственный игровой интеллект).

Чтобы научить Бота играть в игры, он играет с ним каждый день. Сегодня они играют в следующую игру:

Игра начинается с последовательности из $2n$ неотрицательных целых чисел $a_1, a_2, \cdots, a_{2n}$ и числа $S$. Изначально $S = 0$.

Менджи и Бот ходят по очереди; Менджи ходит первым:

  • В свой ход Менджи выбирает число $x$ из последовательности, присваивает $S \leftarrow S \oplus x$ и удаляет $x$ из последовательности. Обратите внимание, что $\oplus$ — это операция побитового исключающего ИЛИ (XOR).
  • В свой ход Бот выбирает число $x$ из последовательности и удаляет $x$ из последовательности.

Игра заканчивается, когда в последовательности не остаётся чисел. Менджи выигрывает тогда и только тогда, когда в конце $S = 0$; в противном случае выигрывает Бот.

Менджи хочет узнать, кто станет победителем игры, если оба игрока будут играть оптимально.

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

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 10^5$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $n$ ($1 \le n \le 10^5$), описанное в условии.

Вторая строка содержит $2n$ целых чисел $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), представляющих числа в игре.

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

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

Для каждого набора входных данных, если Менджи может выиграть игру, выведите в одной строке Menji; в противном случае выведите в одной строке Bot.

Пример

5
2
1 1 3 3
2
1 1 1 3
3
1 1 4 5 1 4
3
1 9 1 9 8 10
6
1 1 4 5 1 4 1 9 1 9 8 10
Bot
Menji
Menji
Menji
Bot

Примечание

В первом наборе входных данных, какое бы число ни выбрал Менджи, Бот всегда может выбрать такое же число, поэтому Менджи всегда выбирает одну $1$ и одну $3$, $S = 1 \oplus 3 = 2 \neq 0$, так что Бот всегда может выиграть.

Во втором наборе входных данных Менджи может выбрать $1$ на первом ходу; что бы ни выбрал Бот, Менджи может выбрать ещё одну $1$, поэтому Менджи всегда получает две $1$, $S = 1 \oplus 1 = 0$, так что Менджи всегда может выиграть.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.