Universal Cup Judging System

Universal Cup

시간 제한: 1.0 s 메모리 제한: 1024 MB 총점: 100
통계

Le Dr Menji est un expert en IA. En ce moment, il entraîne Bot, une AGI (Artificial Game Intelligence).

Pour apprendre à Bot à jouer à des jeux, il joue avec lui tous les jours. Aujourd'hui, ils jouent au jeu suivant :

Le jeu commence avec une suite de $2n$ entiers naturels, $a_1, a_2, \cdots, a_{2n}$, et un nombre $S$. Initialement, $S = 0$.

Menji et Bot jouent à tour de rôle ; Menji commence :

  • Au tour de Menji, il choisit un nombre $x$ de la suite, affecte $S \leftarrow S \oplus x$, et supprime $x$ de la suite. Notez que $\oplus$ est la fonction OU exclusif bit à bit (XOR).
  • Au tour de Bot, il choisit un nombre $x$ de la suite et supprime $x$ de la suite.

Le jeu se termine lorsqu'il ne reste plus aucun nombre dans la suite. Menji gagne si et seulement si $S = 0$ à la fin ; sinon, c'est Bot qui gagne.

Menji se demande qui sera le vainqueur du jeu si les deux joueurs jouent de manière optimale.

Entrée

L'entrée contient plusieurs cas de test. La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 10^5$), décrit dans l'énoncé.

La deuxième ligne contient $2n$ entiers $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), représentant les entiers du jeu.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, si Menji peut gagner la partie, affichez Menji sur une ligne ; sinon, affichez Bot sur une ligne.

Exemple

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

Note

Pour le premier cas de test, quel que soit le nombre choisi par Menji, Bot peut toujours choisir le même nombre, de sorte que Menji choisit toujours un $1$ et un $3$, $S = 1 \oplus 3 = 2 \neq 0$, et Bot peut donc toujours gagner.

Pour le deuxième cas de test, Menji peut choisir un $1$ au premier tour ; quoi que Bot choisisse, Menji peut choisir un autre $1$, de sorte que Menji reçoit toujours deux $1$, $S = 1 \oplus 1 = 0$, et Menji peut donc toujours gagner.

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.