80008 - [ICPC 2025 Shanghai R] AGI

时间限制4s，内存限制512M

题目描述

Dr. Menji is an expert in AI. Now, he is training Bot, an AGI (Artificial Game Intelligence).

To teach Bot how to play games, he plays with Bot every day. Today they are playing the following game:

The game starts with a sequence of 2n non-negative integers, $a_1, a2, \cdots, a{2n}, and a number S. Initially, S = 0$.

Menji and Bot take turns; Menji goes first:

• In Menji’s turn, he chooses a number x from the sequence, sets S \leftarrow S \oplus x, and deletes x from the sequence. Note that \oplus is the bitwise XOR (exclusive or) function.
• In Bot’s turn, he chooses a number x from the sequence and deletes x from the sequence.

The game ends when no numbers remain in the sequence. Menji wins if and only if S = 0 in the end; otherwise, Bot wins.

Menji wonders if both players play optimally, who is the winner of the game.

输入格式

The input contains multiple testcases. The first line contains an integer T (1 \le T \le 10^5), the number of testcases.

For each testcase, the first line contains an integer n (1 \le n \le 10^5), described in the statement.

The second line contains 2n integers $a_1, a2, \cdots, a{2n} (0 \le a_i < 2^{30}$), representing integers in the game.

It’s guaranteed that the sum of n over all testcases does not exceed 2 \times 10^5.

输出格式

For each testcase, if Menji can win the game, print Menji in one line; otherwise, print Bot in one line.

输入输出样例 #1

输入 #1

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

输出 #1

Bot
Menji
Menji
Menji
Bot

说明/提示

For the 1st testcase, no matter what number Menji chooses, Bot can always choose a same number, so Menji always chooses a 1 and a 3, S = 1 \oplus 3 = 2 \ne 0, so Bot can always win.

For the 2nd testcase, Menji can choose a 1 in the first turn; no matter what Bot chooses, Menji can choose another 1, so Menji always receives two 1s, S = 1 \oplus 1 = 0, so Menji can always win.