Олимпиадный тренинг

Задача . D. Игра с билетом


Монокарп и Бикарп живут в Берляндии, где все автобусные билеты состоят из \(n\) цифр, при этом \(n\) — четное число. Гуляя вечером, они нашли билет, некоторые цифры на котором были стерты. Количество позиций, в которых цифры стерты, четно.

Монокарп и Бикарп решили сыграть в игру, используя найденный билет. Монокарп очень не любит счастливые билеты, в то время как Бикарп коллекционирует счастливые билеты. Билет считается счастливым, если сумма первых \(\frac{n}{2}\) цифр билета равна сумме последних \(\frac{n}{2}\) цифр билета.

Монокарп и Бикарп будут ходить по очереди, первый ход сделает Монокарп. На каждом своем ходу игроки будут записывать на место какой-то стертой цифры произвольную цифру от \(0\) до \(9\). Игра заканчивается, когда в билете не останется позиций со стертыми цифрами.

Если в конце игры билет счастливый, то в игре выиграет Бикарп. В противном случае, в игре выиграет Монокарп. Перед вами стоит задача определить победителя игры, если оба игрока будут играть оптимально.

Входные данные

В первой строке следует целое четное число \(n\) \((2 \le n \le 2 \cdot 10^{5})\) — количество цифр в билете.

Во второй строке следует строка, состоящая из \(n\) цифр и знаков «?» — билет, найденный Монокарпом и Бикарпом. Если в позиции \(i\) стоит знак «?», то цифра, стоящая в позиции \(i\) в билете, была стерта. Обратите внимание, что номер билета может содержать лидирующие нули. Количество символов «?» четно.

Выходные данные

Если в игре победит Монокарп, выведите «Monocarp» (без кавычек). В противном случае, выведите «Bicarp» (без кавычек).

Примечание

В первом примере нет ни одной стертой цифры в билете, поэтому игроки не смогут сделать ни одного хода. Так как билет счастливый, то выиграет Бикарп.

Во втором примере выиграет Бикарп, для этого ему нужно поставить на место стертой цифры ту же цифру, которую поставит Монокарп на своем ходу.


Примеры
Входные данныеВыходные данные
1 4
0523
Bicarp
2 2
??
Bicarp
3 8
?054??0?
Bicarp
4 6
???00?
Monocarp

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя