G. Игра над строками
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру со строками.

Изначально у них есть какая-то строка $$$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$$$ для каждой игры. Выясните, кто выиграет каждую игру, если оба игрока умные и играют оптимально.

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

Первая строка содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящую из строчных латинских букв. Это строка, с которой Алиса и Боб привыкли играть.

Вторая строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 10^5$$$) — количество игр.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le |s|$$$) — границы стартовой строки в строке $$$s$$$.

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

Для каждой игры выведите имя игрока, который её выигрывает — «Alice» или «Bob» соответственно.

Примеры
Входные данные
aaab
2
1 2
1 4
Выходные данные
Alice
Bob
Входные данные
aaccbdb
2
5 7
1 7
Выходные данные
Alice
Alice
Примечание

В первом примере:

  1. В первой игре для игры выбрана строка «aa». Алиса удаляет символ «a», после этого Боб не может сделать ход.
  2. Во второй игре для игры выбрана строка «aaab». Какой бы символ не удалила Алиса, Боб удалит оставшийся и Алиса не сможет сделать ход.

Во втором примере Алиса выигрывает и игру со строками «bdb» и «aaccbdb».

Чтобы выиграть в «bdb», Алиса может удалить символ «d», тогда игра продолжится независимо на строках «b» и «b». Боб удаляет одну из этих строк, Алиса удаляет оставшуюся и Боб не может сделать ход.

Чтобы выиграть игру «aaccbdb», Алиса может удалить символ «d», после чего игра будет идти независимо на «aaccb» и «b». Можно показать, что вне зависимости от ходов игроков, эта игра может закончится только за ровно $$$4$$$ хода, а значит, после этого Боб не сможет сделать ход.