Universal Cup Judging System

Universal Cup

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

Dr. Menji er en ekspert på AI. Nå trener han Bot, en AGI (Artificial Game Intelligence).

For å lære Bot hvordan man spiller spill, spiller han med Bot hver dag. I dag spiller de følgende spill:

Spillet starter med en følge av $2n$ ikke-negative heltall, $a_1, a_2, \cdots, a_{2n}$, og et tall $S$. Til å begynne med er $S = 0$.

Menji og Bot bytter på å trekke; Menji starter:

  • I Menjis tur velger han et tall $x$ fra følgen, setter $S \leftarrow S \oplus x$, og sletter $x$ fra følgen. Merk at $\oplus$ er bitvis XOR-funksjonen (eksklusiv eller).
  • I Bots tur velger han et tall $x$ fra følgen og sletter $x$ fra følgen.

Spillet slutter når det ikke er flere tall igjen i følgen. Menji vinner hvis og bare hvis $S = 0$ til slutt; ellers vinner Bot.

Menji lurer på hvem som vinner spillet dersom begge spillerne spiller optimalt.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($1 \le n \le 10^5$), som beskrevet i oppgaveteksten.

Den andre linjen inneholder $2n$ heltall $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), som representerer heltallene i spillet.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle, hvis Menji kan vinne spillet, skriv ut Menji på én linje; ellers, skriv ut Bot på én linje.

Eksempel

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

Merk

For det første testtilfellet kan Bot, uansett hvilket tall Menji velger, alltid velge et likt tall, slik at Menji alltid velger én $1$-er og én $3$-er, $S = 1 \oplus 3 = 2 \neq 0$, så Bot kan alltid vinne.

For det andre testtilfellet kan Menji velge én $1$-er i første trekk; uansett hva Bot velger, kan Menji velge en annen $1$-er, slik at Menji alltid får to $1$-ere, $S = 1 \oplus 1 = 0$, så Menji kan alltid vinne.

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.