Ticket Game
Contest: Codeforces Round 585 (Div. 2)
Difficulty rating: 1700
Tags: games, greedy, math

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.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
0523

Example output:
Bicarp

Example input:
2
??

Example output:
Bicarp

Editorial:
Let's denote the balance as the difference between the sum of digits in the left half and the sum of digits in the right half. Also let $$$L$$$ be the minimum possible balance (it can be calculated if we replace all question marks in the left half with $$$0$$$'s and all the question marks in the right half with $$$9$$$'s), and let $$$R$$$ be the maximum possible balance.
The second player wins if and only if $$$\frac{L + R}{2} = 0$$$. Let's prove it by induction on the number of question marks left in the ticket.
If all characters are digits, the second player wins only if the ticket is happy, and that is when $$$\frac{L + R}{2} = 0$$$.
Okay, now suppose the number of question marks is even, and now it's first player's turn. Each turn decreases the value of $$$R - L$$$ by $$$9$$$, and may set $$$L$$$ to any number from current $$$L$$$ to $$$L + 9$$$. If $$$L + R > 0$$$, then the first player can make $$$L$$$ as large as possible, and set it to $$$L + 9$$$. The best thing the second player can do on his turn is to set $$$R$$$ to $$$R - 9$$$ (and leave $$$L$$$ as it is), and the value of $$$L + R$$$ will be the same as it was two turns earlier. The case $$$L + R < 0$$$ can be analyzed similarly. And in the case $$$L + R = 0$$$ the second player has a symmetric strategy.