Universal Cup Judging System

Universal Cup

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

Доктор Менджи — жасанды интеллект саласының сарапшысы. Қазір ол AGI (Artificial Game Intelligence — жасанды ойын интеллектісі) болып табылатын Ботты жаттықтырып жатыр.

Ботқа ойын ойнауды үйрету үшін ол күн сайын Ботпен ойнайды. Бүгін олар келесі ойынды ойнап жатыр:

Ойын $2n$ теріс емес бүтін саннан тұратын $a_1, a_2, \cdots, a_{2n}$ тізбегінен және $S$ санынан басталады. Бастапқыда $S = 0$.

Менджи мен Бот кезектесіп жүреді; Менджи бірінші бастайды:

  • Менджи өз кезегінде тізбектен бір $x$ санын таңдап, $S \leftarrow S \oplus x$ деп орнатады да, тізбектен $x$ санын өшіреді. Мұндағы $\oplus$ — биттік XOR (ажыратқыш НЕМЕСЕ) функциясы екенін ескеріңіз.
  • Бот өз кезегінде тізбектен бір $x$ санын таңдап, тізбектен $x$ санын өшіреді.

Тізбекте ешқандай сан қалмаған кезде ойын аяқталады. Менджи соңында $S = 0$ болса және тек сонда ғана жеңеді; әйтпесе Бот жеңеді.

Менджи екі ойыншы да тиімді (оптималды) ойнаса, ойында кім жеңімпаз болатынын білгісі келеді.

Кіріс деректер

Кіріс деректер бірнеше тест жиынтығынан тұрады. Бірінші жолда тесттер санын білдіретін бүтін сан $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 деп шығарыңыз; әйтпесе бір жолға 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

Ескертпе

Бірінші тест жиынтығы үшін Менджи қандай санды таңдаса да, Бот әрқашан дәл сондай санды таңдай алады, сондықтан Менджи әрқашан бір $1$ мен бір $3$ санын таңдайды, $S = 1 \oplus 3 = 2 \neq 0$, демек Бот әрқашан жеңе алады.

Екінші тест жиынтығы үшін Менджи бірінші жүрісте $1$ санын таңдай алады; Бот не таңдаса да, Менджи тағы бір $1$ санын таңдай алады, сондықтан Менджи әрқашан екі $1$ санын алады, $S = 1 \oplus 1 = 0$, демек Менджи әрқашан жеңе алады.

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.