Алиса и Боб играют в игру со строками. Всего в игре будет \(t\) раундов. В каждом раунде будет строка \(s\), состоящая из строчных латинских букв.
Оба игрока делают ходы по очереди, Алиса ходит первой. Алиса может удалить любую подстроку чётной длины (возможно пустую) и Боб может удалить любую подстроку нечётной длины из \(s\).
Более формально, если была строка \(s = s_1s_2 \ldots s_k\) игрок может выбрать подстроку \(s_ls_{l+1} \ldots s_{r-1}s_r\) длины соответствующей чётности и удалить её. После этого строка станет \(s = s_1 \ldots s_{l-1}s_{r+1} \ldots s_k\).
Когда строка становится пустой, раунд заканчиваются и каждый игрок считает его/её очки за этот раунд. Количество очков игрока равно сумме стоимостей символов, удалённых им/ей. Стоимость \(\texttt{a}\) равна \(1\), стоимость \(\texttt{b}\) равна \(2\), стоимость \(\texttt{c}\) равна \(3\), \(\ldots\), и стоимость \(\texttt{z}\) равна \(26\). Игрок с большим количеством очков побеждает в раунде. Для каждого раунда определите победителя и разницу очков победителя и проигравшего. Считайте, что оба игрока играют оптимально с целью максимизировать свои очки. Можно доказать, что ничья невозможна.
Выходные данные
Для каждого раунда выведите единственную строку, содержащую строку и число. Если Алиса выиграет в раунде, строка должна быть «Alice». Если Боб выигрывает в раунде, строка должна быть «Bob». Число должно быть равно разности очков, если оба игрока играют оптимально.
Примечание
В первом раунде \(\texttt{"aba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{ab}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}\). Общее количество очков Алисы равно \(1+2=3\). Общее количество очков Боба равно \(1\).
Во втором раунде \(\texttt{"abc"}\xrightarrow{\texttt{Alice}}\texttt{"a}{\color{red}{\texttt{bc}}}\texttt{"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}\). Общее количество очков Алисы равно \(2+3=5\). Общее количество очков Боба равно \(1\).
В третьем раунде \(\texttt{"cba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{cb}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}\). Общее количество очков Алисы равно \(3+2=5\). Общее количество очков Боба равно \(1\).
В четвёртом раунде \(\texttt{"n"}\xrightarrow{\texttt{Alice}}\texttt{"n"}\xrightarrow{} \texttt{"n"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{n}}}\texttt{"}\xrightarrow{}\texttt{""}\). Общее количество очков Алисы равно \(0\). Общее количество очков Боба равно \(14\).
В пятом раунде \(\texttt{"codeforces"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{codeforces}}}\texttt{"}\xrightarrow{} \texttt{""}\). Общее количество очков Алисы равно \(3+15+4+5+6+15+18+3+5+19=93\). Общее количество очков Боба равно \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
aba
abc
cba
n
codeforces
|
Alice 2
Alice 4
Alice 4
Bob 14
Alice 93
|