Alice 和 Bob 正在玩弦乐游戏。游戏中将会有 $$$t$$$ 轮。每轮都会出现一个由小写英文字母组成的字符串$$$s$$$。
Alice 首先行动,两名玩家轮流行动。 Alice 可以从 $$$s$$$ 中删除任何偶数长度的子字符串(可能为空),而 Bob 可以从 $$$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$$$。得分较高的玩家赢得该回合。对于每一轮,确定获胜者以及获胜者和失败者分数之间的差异。假设两名玩家都以最佳方式发挥以最大化他们的分数。可以证明平局是不可能的。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 5\cdot 10^4$$$) 表示轮数。
接下来的 $$$t$$$ 行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1\leq |s|\leq 2\cdot 10^5$$$),表示该轮使用的字符串。这里$$$|s|$$$表示字符串$$$s$$$的长度。
保证所有回合的$$$|s|$$$总和不超过$$$2\cdot 10^5$$$。
输出
对于每一轮,打印一行包含一个字符串和一个整数。如果爱丽丝赢得了这一轮,则该字符串必须是“爱丽丝”。如果鲍勃赢得了这一轮,则该字符串必须是“鲍勃”。假设两个玩家都发挥最佳,该整数必须是他们分数之间的差值。
示例
输入 #1
5 aba abc cba n codeforces
输出 #1
Alice 2 Alice 4 Alice 4 Bob 14 Alice 93
注意
第一轮,$$$\texttt{"aba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{ab}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{鲍勃}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$。 Alice的总分是$$$1+2=3$$$。鲍勃的总分是 $$$1$$$。
第二轮,$$$\texttt{"abc"}\xrightarrow{\texttt{Alice}}\texttt{"a}{\color{red}{\texttt{bc}}}\texttt{"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{鲍勃}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$。 Alice的总分是$$$2+3=5$$$。鲍勃的总分是 $$$1$$$。
第三轮,$$$\texttt{"cba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{cb}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{鲍勃}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$$$。 Alice的总分是$$$3+2=5$$$。鲍勃的总分是 $$$1$$$。
第四轮,$$$\texttt{"n"}\xrightarrow{\texttt{Alice}}\texttt{"n"}\xrightarrow{} \texttt{"n"}\xrightarrow{\texttt{鲍勃}}\texttt{"}{\color{red}{\texttt{n}}}\texttt{"}\xrightarrow{}\texttt{""}$$$。爱丽丝的总分是$$$0$$$。鲍勃的总分是 $$$14$$$。
第五轮,$$$\texttt{"codeforces"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{codeforces}}}\texttt{"}\xrightarrow{} \texttt{""}$$$。 Alice的总分是$$$3+15+4+5+6+15+18+3+5+19=93$$$。鲍勃的总分是 $$$0$$$。