Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100
Statistics

Dr. Menji ist ein KI-Experte. Derzeit trainiert er Bot, eine AGI (Artificial Game Intelligence).

Um Bot beizubringen, wie man Spiele spielt, spielt er jeden Tag mit Bot. Heute spielen sie das folgende Spiel:

Das Spiel beginnt mit einer Folge von $2n$ nichtnegativen ganzen Zahlen, $a_1, a_2, \cdots, a_{2n}$, und einer Zahl $S$. Zu Beginn gilt $S = 0$.

Menji und Bot sind abwechselnd am Zug; Menji beginnt:

  • In Menjis Zug wählt er eine Zahl $x$ aus der Folge, setzt $S \leftarrow S \oplus x$ und löscht $x$ aus der Folge. Beachte, dass $\oplus$ die bitweise XOR-Funktion (Exklusiv-Oder) ist.
  • In Bots Zug wählt er eine Zahl $x$ aus der Folge und löscht $x$ aus der Folge.

Das Spiel endet, wenn keine Zahlen mehr in der Folge übrig sind. Menji gewinnt genau dann, wenn am Ende $S = 0$ gilt; andernfalls gewinnt Bot.

Menji fragt sich, wer das Spiel gewinnt, wenn beide Spieler optimal spielen.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 10^5$), wie in der Aufgabenstellung beschrieben.

Die zweite Zeile enthält $2n$ ganze Zahlen $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), welche die ganzen Zahlen im Spiel darstellen.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall in einer Zeile Menji aus, falls Menji das Spiel gewinnen kann; andernfalls gib in einer Zeile Bot aus.

Beispiel

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

Hinweis

Für den ersten Testfall kann Bot unabhängig davon, welche Zahl Menji wählt, immer dieselbe Zahl wählen, sodass Menji immer eine $1$ und eine $3$ wählt, $S = 1 \oplus 3 = 2 \neq 0$, weshalb Bot immer gewinnen kann.

Für den zweiten Testfall kann Menji im ersten Zug eine $1$ wählen; unabhängig davon, was Bot wählt, kann Menji eine weitere $1$ wählen, sodass Menji immer zwei $1$en erhält, $S = 1 \oplus 1 = 0$, weshalb Menji immer gewinnen kann.

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.