#P17128. [ICPC 2025 Shanghai R] AGI

    ID: 19465 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>数学贪心博弈论2025上海位运算ICPC分类讨论

[ICPC 2025 Shanghai R] AGI

Problem Description

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 2n2n non-negative integers, a1,a2,,a2na_1, a_2, \cdots, a_{2n}, and a number SS. Initially, S=0S = 0.

Menji and Bot take turns; Menji goes first:

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

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

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

Input Format

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

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

The second line contains 2n2n integers a1,a2,,a2na_1, a_2, \cdots, a_{2n} (0ai<2300 \le a_i < 2^{30}), representing integers in the game.

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

Output Format

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

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

Hint

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

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