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.