Ticket Game

题意翻译

### 题目描述 ``Monocarp``和``Bicarp``生活在``Berland``。``Berland``的每一张公交车票都包含$n$（$n$是偶数）位数。 在晚上散步时，``Monocarp``和``Bicarp``发现了一张有某些位被擦掉而空着（擦掉的位数也是偶数）的公交车票。 ``Monocarp``讨厌“高兴”的车票，而``Bicarp``则喜欢并收集它们。我们称一张车票“高兴”是说前$\frac n 2$位数之和和后$\frac n 2$位数之和相等。 ``Monocarp``和``Bicarp``轮流进行操作（``Monocarp``先手），每次操作，当前进行操作的玩家会在一个被空着的数位填上$0$到$9$。当所有数位都被填满，游戏结束。 如果这张车票在游戏结束后“高兴”，那么``Bicarp``胜利；否则``Monocarp``胜利。如果两人都足够聪明，请你确定谁会胜出。 ### 输入格式 第一行一个整数$n$，表示车票的位数。 第二行包含一个长度为$n$的字符串，由$0$到$9$和``?``组成，表示两人发现的这张车票。``?``表示这一位被擦去了。保证``?``有偶数个。注意，车票可以有前导零。 ### 输出格式 如果``Monocarp``最终会胜出，输出``Monocarp``。否则输出``Bicarp``。 ### 说明/提示 样例一中没有任何问号，所以赢家在游戏开始前就决定了，显然就是``Bicarp``。 在样例二中，``Bicarp``也会赢。在``Monocarp``在一个空位填上一个数之后，``Bicarp``可以在另一个空位填上一个一样的数，于是车票就变得“高兴”了。

题目描述

Monocarp and Bicarp live in Berland, where every bus ticket consists of $ n $ digits ( $ n $ is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even. Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first $ \frac{n}{2} $ digits of this ticket is equal to the sum of the last $ \frac{n}{2} $ digits. Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from $ 0 $ to $ 9 $ . The game ends when there are no erased digits in the ticket. If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.

输入输出格式

输入格式

The first line contains one even integer $ n $ $ (2 \le n \le 2 \cdot 10^{5}) $ — the number of digits in the ticket. The second line contains a string of $ n $ digits and "?" characters — the ticket which Monocarp and Bicarp have found. If the $ i $ -th character is "?", then the $ i $ -th digit is erased. Note that there may be leading zeroes. The number of "?" characters is even.

输出格式

If Monocarp wins, print "Monocarp" (without quotes). Otherwise print "Bicarp" (without quotes).

输入输出样例

输入样例 #1

4
0523

输出样例 #1

Bicarp

输入样例 #2

2
??

输出样例 #2

Bicarp

输入样例 #3

8
?054??0?

输出样例 #3

Bicarp

输入样例 #4

6
???00?

输出样例 #4

Monocarp

说明

Since there is no question mark in the ticket in the first example, the winner is determined before the game even starts, and it is Bicarp. In the second example, Bicarp also wins. After Monocarp chooses an erased digit and replaces it with a new one, Bicap can choose another position with an erased digit and replace it with the same digit, so the ticket is happy.