Алиса и Боб играют в игру. В строке \(n\) ячеек. Изначально каждая ячейка либо красная, либо синяя. Алиса ходит первой.
На каждом ходу Алиса выбирает две соседние клетки, в которых есть хотя бы одна красная клетка, и окрашивает эти две клетки в белый цвет. Затем Боб выбирает две соседние клетки, содержащие хотя бы одну синюю клетку, и окрашивает эти две клетки в белый цвет. Игрок, который не может сделать ход, проигрывает.
Определите победителя, если и Алиса, и Боб играют оптимально.
Обратите внимание, что выбранная ячейка может быть белой, если другая ячейка удовлетворяет ограничениям.
Выходные данные
Для каждого набора входных данных выведите имя победителя в отдельной строке.
Примечание
В первом наборе входных данных у Алисы есть два варианта: закрасить первую и вторую клетки или закрасить вторую и третью клетки. Какой бы выбор ни сделала Алиса, после хода Алисы останется ровно одна синяя клетка. Бобу нужно просто закрасить синюю клетку и ее соседнюю, тогда каждая клетка будет белой и Алиса не сможет сделать ход. Итак, Боб — победитель.
Во втором наборе входных данных независимо от того, что выберет Алиса, Боб может закрасить четвертую и пятую клетки за \(2\) хода.
В третьем наборе входных данных сначала Алиса красит третью и четвертую клетки. Неважно, закрашивает ли Боб первую и вторую клетки или пятую и шестую, Алиса может закрасить две другие клетки.
В четвертом наборе входных данных сначала Алиса красит вторую и третью клетки. Если Боб закрашивает пятую и шестую клетки или четвертую и пятую клетки, то Алиса закрашивает седьмую и восьмую клетки. Если Боб закрашивает седьмую и восьмую клетки, то Алиса закрашивает пятую и шестую клетки.
В пятом наборе входных данных Алиса сначала выбирает две средние клетки, затем у Боба, очевидно, есть только два варианта, какой бы вариант он ни выбрал, Алиса может выбрать другой и выиграть.
В восьмом наборе входных данных независимо от того, что выберет Алиса, Боб может выбрать две другие симметричные ячейки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3
BRB
5
RRBBB
6
RBRBRB
8
BBRRBRRB
6
BRRBRB
12
RBRBRBRBRRBB
12
RBRBRBRBBBRR
4
RBBR
|
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
|