eolymp
bolt
Try our new interface for solving problems
Problems

Royal Croquet 2

Royal Croquet 2

Time limit 1 second
Memory limit 64 MiB

– Все по местам! - закричала Королева громовым голосом. И все побежали, натыкаясь друг на друга, падая и вскакивая. Однако через минуту все уже стояли на своих местах. Игра началась.

Алиса подумала, что в жизни не видала такой странной площадки для игры в крокет: сплошные рытвины и борозды. Шарами служили ежи, молотками - фламинго, а воротцами - солдаты. Они делали мостик - да так и стояли всю игру.

Поначалу Алиса никак не могла справиться со своим фламинго: только сунет его вниз головой под мышку, отведет ему ноги назад, нацелится и соберется ударить им по ежу, как он изогнет шею и поглядит ей прямо в глаза, да так удивленно, что она начинает смеяться; а когда ей удается снова опустить его вниз головой, глядь! - ежа уже нет, он развернулся и тихонько трусит себе прочь. К тому же все ежи у нее попадали в рытвины, а солдаты-воротца разгибались и уходили на другой конец площадки. Словом, Алиса скоро решила, что это очень трудная игра.

Приключения Алисы в стране чудес (перевод Н.М. Демуровой)

Помимо странной площадки и живого спортинвентаря не менее странными и запутанными были правила этой чудо-игры. Игроки били все сразу, не дожидаясь своей очереди, и все время ссорились и дрались из-за ежей; в скором времени Королева пришла в бешенство, топала ногами и то и дело кричала:

– Отрубить ей голову! Голову ему долой!

Тем не менее, правила все же имеются.

Играть могут от 2 до 5 игроков. Игроки по очереди бьют по своим ежам, стараясь попасть в ворота.

Подача

Каждый розыгрыш очка начинается с подачи. Право подачи постоянно в течение игры переходит от одного игрока к другому по кругу.

Гейм

Каждый гейм начинается с нулевого счета. За первые два попадания в ворота игрок получает по 15 очков, а за третье - еще 10. Следующее попадание приводит к выигрышу гейма в случае, если противники имеют счет 30 или меньше. Если все игроки имеют по 40, то выигрыш следующей подачи дает преимущество. Игрок, имеющий преимущество и выигравший следующую подачу, побеждает в гейме.

Сет

Игрок, выигравший 6 геймов, считается выигравшим сет. Если после 6 сетов следующий за лидером игрок набрал 5 очков, то разыгрывается еще один гейм. Если разрыв увеличивается, то сет заканчивается. В противном случае разыгрывается тай-брейк.

Матч

Матч может быть 3–сетовым или 5–сетовым (по желанию Червовой Королевы). В 3-сетовом побеждает игрок выигравший 2 сета, в 5-сетовом – 3 сета. Остальным Королева приказывает отрубить головы, но поскольку палач обычно начинает пререкаться, жаловаться на маленькую зарплату, радикулит и тупой топор, делается это крайне редко.

Тай-брейк

Игроки по очереди делают по одному удару. Первый, кто наберет 7 очков с разницей в 2 очка, считается выигравшим тай-брейк. Тай-брейк длится столько, сколько необходимо, пока не будет достигнута разница в два очка. Последний сет в игре играется без тай-брейка.

За всей игрой, задумчиво улыбаясь, наблюдал Чеширский кот и записывал протокол игры – т.е. игрока, выигравшего в каждой подаче. Определите, кто же победил в этом замечательном состязании.

Input data

Входной файл состоит из нескольких строк, каждая из которых описывает отдельную игру. Каждая строка содержит протокол игры: сначала целое число N (2N 5) – количество игроков, далее – строка из больших букв английского алфавита. Каждая буква в строке обозначает игрока (А – первый, В – второй и т.д.), который выиграл подачу. Количество букв не превосходит 100000.

Output data

В выходной файл для каждой игры в отдельной строке выведите единственный символ, который будет обозначать победителя в соответствующей игре.

Examples

Input example #1
2 BBABABAAABBBABBBABBBBABBBBAABBBABBBBBBABAAAABBABABAAAABABBABAAAABAABABABBBAAABBBBAABABABABBAABABBBBBBAAAABBAAAABAABBBBAABBABABABBABABBAABBBAABABABABABBBBAAABBABBBBBAAAAAABBABAAABBBABAABABBBAABAAABAABBBBBAAABBABBBBBAABAABBABB
2 BAAABBABABBBAABABBBAABBBABBAABABABBAABBBABBBAABAABABBABABAAAAABBBAAABABAABBABABAAAAABBABBAABABAABBBABBBBBABBABAAAAAAABABBAAAABABABAAAABBAAAAAAABBAABBAAABABABBABABBABBBAAABBABABBABAAABAABABABBAABBABBBABBBBBAABAABBABABBBABAABABABABABABABABABBABABABABAABABABBAABBABBAAAAAAAABABBAAABBABABABABAABAAABBABBBABAAAABABABABBBBBBAAABAAAAABABBABAABBBAABAAABBBBBBBABAABABABABABABABABABABAAAAABBAABBBAAABABAAAABAABBBABAABABABBAABABBBAAABBBBBBAABABBAABBAABBAABABABBAABABBBBAAAABBBAAABBBAAABBABABABABBBBABABABBABBBBABAABBABBABBAABBBABBBBBB
2 BABABBABABBBBBAABABAAABABBAABABBABBBBABBBAAABBAABABBABAABBABAABAABABABBABAAABAAABBBAAABBBAAAABBABAAABBBABABBBAABABAAABABBAABAABBABABABABABABAAABBBAABAAABBBABABABABBAABBAABABABBAABABBABABBBBAABABAABAABABAAAABAAAAAABBBABBBAABBBBBAABABBBAABABBBAABA
...
Output example #1
B
B
A
A
A
B
A
B
B
A
B
B
B
B
B
B
A
B
A
B
Author Arzubov Nikolay
Source VI Open Cup Kharkov 14.03.2010