Алиса и Боб играют в игру. Изначально им дана непустая строка \(s\), состоящая из строчных латинских букв. Длина строки четная. У каждого игрока также есть своя строка, изначально пустая.
Алиса начинает, затем они ходят по очереди. За один ход игрок берет либо первую, либо последнюю букву из строки \(s\), удаляет ее из \(s\) и приписывает ее в начало своей строки.
Игра заканчивается, когда строка \(s\) становится пустой. Побеждает игрок, у которого строка лексикографически меньше. Если строки у игроков одинаковые, то это ничья.
Строка \(a\) лексикографически меньше строки \(b\), если существует такая позиция \(i\), что \(a_j = b_j\) для всех \(j < i\) и \(a_i < b_i\).
С каким результатом закончится игра, если оба игрока играют оптимально (т. е. оба игрока стараются выиграть; если они не могут, то стараются сыграть вничью)?
Выходные данные
На каждый набор входных данных выведите результат игры, если оба игрока играют оптимально. Если Алиса выиграет, то выведите «Alice». Если Боб выиграет, то выведите «Bob». Если игра закончится вничью, то выведите «Draw».
Примечание
Одна из возможных игр, которую могут сыграть Алиса и Боб в первом наборе входных данных:
- Алиса выбирает первую букву в \(s\): \(s=\)«orces», \(a=\)«f», \(b=\)«»;
- Боб выбирает последнюю букву в \(s\): \(s=\)«orce», \(a=\)«f», \(b=\)«s»;
- Алиса выбирает последнюю букву в \(s\): \(s=\)«orc», \(a=\)«ef», \(b=\)«s»;
- Боб выбирает первую букву в \(s\): \(s=\)«rc», \(a=\)«ef», \(b=\)«os»;
- Алиса выбирает последнюю букву в \(s\): \(s=\)«r», \(a=\)«cef», \(b=\)«os»;
- Боб выбирает оставшуюся букву в \(s\): \(s=\)«», \(a=\)«cef», \(b=\)«ros».
Алиса выигрывает, потому что «cef» < «ros». Ни один из игроков не следует никакой стратегии в конкретно этой игре, поэтому она не показывает, что Алиса выигрывает, если игроки играют оптимально.