本文共 2680 字，大约阅读时间需要 8 分钟。

Monocarp and Bicarp live in Berland, where every bus ticket consists of nn digits (nn 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 n2n2 digits of this ticket is equal to the sum of the last n2n2 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 00 to 99. 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

The first line contains one even integer nn (2≤n≤2⋅105)(2≤n≤2⋅105) — the number of digits in the ticket.

The second line contains a string of nn digits and “?” characters — the ticket which Monocarp and Bicarp have found. If the ii-th character is “?”, then the ii-th digit is erased. Note that there may be leading zeroes. The number of “?” characters is even.

Output

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

Examples

Input 4 0523 Output Bicarp Input 2 ?? Output Bicarp Input 8 ?054??0? Output Bicarp Input 6 ???00? Output Monocarp 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.

挺好的一道博弈的题目，虽然我不会做。。 题意：一个数字序列由n（n为整数且小于2e5）位组成,其中有整数个数位被污染，现在A和B可以轮流给被污染数位赋值（0-9），A先来，若最后序列前后两端数位和不等，A赢，否则B赢，两方都选最优策略。 思路：我看网上有什么很高深的证明啥的，但是俺也不会。。 如果没有问号的话，我们就判断左右两半的和是否相等。 如果有问号，而且某一边的和大于另一边，而且问号数量也大于另一边。那么M就可以往这一边放大的，M就能赢了。 接下来的情况就是在剩下的一方里（假设此时还剩n个污染部位），还是A先手，两方每次选择一个0~9之间的数，如果最后选择数的和等于初始左右差值，B赢，否则A赢

这就转换为一个经典博弈问题了，只要n/2*9==差值，B赢，否则A赢。

想想为什么，因为后手的B只可以控制他和A选择的数的总和是9，故如果轮数乘9和差值相等就赢，否则就输。

代码如下：

#include
   
    #define ll long longusing namespace std;string s;int n;int main(){
   	cin>>n>>s;	int sum1=0,sum2=0,lsum=0,rsum=0;	int m=n%2?n/2+1:n/2;	for(int i=0;i
    
     sum2&&lsum>rsum)||(sum2>sum1&&rsum>lsum)) puts("Monocarp");	else	{
   		int cnt=(9*abs(sum1-sum2)/2);		if(cnt!=abs(lsum-rsum)) puts("Monocarp");		else puts("Bicarp");	}}
    
   

多思考一下吧，博弈真的感觉有心无力。。

努力加油a啊，(^o)/~

转载地址：http://fftvi.baihongyu.com/