Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100
İstatistikler

Menji 博士係一位人工智能專家。宜家,佢正在訓練一個 AGI(Artificial Game Intelligence,人工遊戲智能)— Bot。

為咗教識 Bot 點樣玩遊戲,佢每日都會同 Bot 玩遊戲。今日佢哋玩緊下面呢個遊戲:

遊戲開始嗰陣有一個由 $2n$ 個非負整數組成嘅序列 $a_1, a_2, \cdots, a_{2n}$,同埋一個數 $S$。一開始,$S = 0$。

Menji 同 Bot 輪流行動,由 Menji 先手:

  • 喺 Menji 嘅回合,佢會從序列入面揀一個數 $x$,將 $S$ 更新為 $S \leftarrow S \oplus x$,然後從序列入面刪除 $x$。注意 $\oplus$ 係按位異或(XOR)運算。
  • 喺 Bot 嘅回合,佢會從序列入面揀一個數 $x$,然後從序列入面刪除 $x$。

當序列入面冇晒數字嗰陣,遊戲就會結束。當且僅當最後 $S = 0$ 嗰陣 Menji 贏;否則 Bot 贏。

Menji 想知道,如果雙方都採取最優策略,邊個會係呢場遊戲嘅贏家。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $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 可以贏得遊戲,喺一行入面輸出 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

提示

對於第一組測試資料,無論 Menji 揀邊個數,Bot 總可以揀一個相同嘅數,所以 Menji 一定會揀到一個 $1$ 同埋一個 $3$,$S = 1 \oplus 3 = 2 \neq 0$,因此 Bot 一定可以贏。

對於第二組測試資料,Menji 可以喺第一回合揀一個 $1$;無論 Bot 揀咩,Menji 都可以揀另一個 $1$,所以 Menji 總會攞到兩個 $1$,$S = 1 \oplus 1 = 0$,因此 Menji 一定可以贏。

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.