Алиса и Боб играют в игру со строками.
Изначально у них есть какая-то строка \(t\). За один ход первый игрок выбирает какой-то символ \(c\), присутствующий в строке \(t\), и удаляет все его вхождения в \(t\), тем самым разбивая \(t\) на много меньших строк. Игра затем продолжается на этих строках независимо: чтобы сделать ход, игрок должен выбрать одну из строк и один символ из неё, удалить все его вхождения, и вернуть получившиеся строки назад в игру.
Алиса начинает игру, после чего Алиса и Боб ходят по очереди. Игрок, который не может сделать ход (потому что не осталось ни одной строки), проигрывает.
Алиса и Боб привыкли играть со строкой \(s\), но недавно им стало это надоедать. Теперь перед каждой игрой они выбирают два целых числа \(l\) и \(r\) такие, что \(1 \le l \le r \le |s|\) и играют вместо этого на строке \(s_{l} s_{l+1} s_{l+2} \ldots s_{r}\).
Вам дана строка \(s\) и целые числа \(l\) и \(r\) для каждой игры. Выясните, кто выиграет каждую игру, если оба игрока умные и играют оптимально.
Выходные данные
Для каждой игры выведите имя игрока, который её выигрывает — «Alice» или «Bob» соответственно.
Примечание
В первом примере:
- В первой игре для игры выбрана строка «aa». Алиса удаляет символ «a», после этого Боб не может сделать ход.
- Во второй игре для игры выбрана строка «aaab». Какой бы символ не удалила Алиса, Боб удалит оставшийся и Алиса не сможет сделать ход.
Во втором примере Алиса выигрывает и игру со строками «bdb» и «aaccbdb».
Чтобы выиграть в «bdb», Алиса может удалить символ «d», тогда игра продолжится независимо на строках «b» и «b». Боб удаляет одну из этих строк, Алиса удаляет оставшуюся и Боб не может сделать ход.
Чтобы выиграть игру «aaccbdb», Алиса может удалить символ «d», после чего игра будет идти независимо на «aaccb» и «b». Можно показать, что вне зависимости от ходов игроков, эта игра может закончится только за ровно \(4\) хода, а значит, после этого Боб не сможет сделать ход.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaab
2
1 2
1 4
|
Alice
Bob
|
|
2
|
aaccbdb
2
5 7
1 7
|
Alice
Alice
|