Universal Cup Judging System

Universal Cup

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

Dr. Menji adalah seorang pakar AI. Saat ini, ia sedang melatih Bot, sebuah AGI (Artificial Game Intelligence).

Untuk mengajari Bot cara bermain gim, ia bermain bersama Bot setiap hari. Hari ini mereka memainkan gim berikut:

Gim dimulai dengan sebuah barisan yang terdiri dari $2n$ bilangan bulat non-negatif, $a_1, a_2, \cdots, a_{2n}$, dan sebuah bilangan $S$. Pada awalnya, $S = 0$.

Menji dan Bot bermain secara bergiliran; Menji jalan terlebih dahulu:

  • Pada giliran Menji, ia memilih sebuah bilangan $x$ dari barisan, mengubah $S \leftarrow S \oplus x$, lalu menghapus $x$ dari barisan. Perhatikan bahwa $\oplus$ adalah fungsi bitwise XOR (exclusive or).
  • Pada giliran Bot, ia memilih sebuah bilangan $x$ dari barisan dan menghapus $x$ dari barisan.

Gim berakhir ketika tidak ada lagi bilangan yang tersisa di dalam barisan. Menji menang jika dan hanya jika $S = 0$ pada akhir permainan; jika tidak, Bot yang menang.

Menji ingin tahu jika kedua pemain bermain secara optimal, siapakah pemenang dari gim tersebut.

Masukan

Masukan terdiri atas beberapa kasus uji. Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$), seperti yang dijelaskan pada deskripsi soal.

Baris kedua berisi $2n$ bilangan bulat $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), yang menyatakan bilangan-bilangan bulat di dalam gim.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, jika Menji dapat memenangkan gim, cetak Menji dalam satu baris; jika tidak, cetak Bot dalam satu baris.

Contoh

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

Catatan

Untuk kasus uji pertama, bilangan apa pun yang dipilih Menji, Bot selalu dapat memilih bilangan yang sama, sehingga Menji selalu memilih satu bilangan $1$ dan satu bilangan $3$, $S = 1 \oplus 3 = 2 \neq 0$, sehingga Bot selalu dapat menang.

Untuk kasus uji kedua, Menji dapat memilih sebuah bilangan $1$ pada giliran pertama; apa pun yang dipilih Bot, Menji dapat memilih bilangan $1$ lainnya, sehingga Menji selalu mendapatkan dua bilangan $1$, $S = 1 \oplus 1 = 0$, sehingga Menji selalu dapat menang.

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.