Letter Picking

题意翻译

### 题目描述 Alice 和 Bob 在玩游戏。 给出一个长度为偶数的，非空的且仅含小写字母的字符串 $s$。每个玩家还拥有一个初始为空的字符串。 Alice 先手，两名玩家交替行动。在一次行动中，玩家可以取 $s$ 首或尾字符，将其从 $s$ 中移除后加入到自己的字符串的 **最前面**。 当 $s$ 为空时游戏结束，拥有字典序更小的字符串的玩家获胜。若两名玩家的字符串相等则平局。 若 Alice 和 Bob 都足够聪明，判断谁会取胜，或者游戏为平局。 数据组数 $t\leq 10^3$，$\sum|s|\leq 2\times 10^3$。保证所有输入的 $|s|$ 长度都为偶数。

题目描述

Alice and Bob are playing a game. Initially, they are given a non-empty string $ s $ , consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty. Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $ s $ , removes it from $ s $ and prepends (adds to the beginning) it to their own string. The game ends when the string $ s $ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw. A string $ a $ is lexicographically smaller than a string $ b $ if there exists such position $ i $ that $ a_j = b_j $ for all $ j < i $ and $ a_i < b_i $ . What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of testcases. Each testcase consists of a single line — a non-empty string $ s $ , consisting of lowercase Latin letters. The length of the string $ s $ is even. The total length of the strings over all testcases doesn't exceed $ 2000 $ .

输出格式

For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

输入输出样例

输入样例 #1

2
forces
abba

输出样例 #1

Alice
Draw

说明

One of the possible games Alice and Bob can play in the first testcase: 1. Alice picks the first letter in $ s $ : $ s= $ "orces", $ a= $ "f", $ b= $ ""; 2. Bob picks the last letter in $ s $ : $ s= $ "orce", $ a= $ "f", $ b= $ "s"; 3. Alice picks the last letter in $ s $ : $ s= $ "orc", $ a= $ "ef", $ b= $ "s"; 4. Bob picks the first letter in $ s $ : $ s= $ "rc", $ a= $ "ef", $ b= $ "os"; 5. Alice picks the last letter in $ s $ : $ s= $ "r", $ a= $ "cef", $ b= $ "os"; 6. Bob picks the remaining letter in $ s $ : $ s= $ "", $ a= $ "cef", $ b= $ "ros". Alice wins because "cef" &lt; "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

**题目大意**：

爱丽丝和鲍勃在玩一个游戏。游戏开始时，他们得到一个由小写拉丁字母组成的非空字符串 $ s $，字符串的长度是偶数。每位玩家自己也有一个初始为空的字符串。

爱丽丝先开始，然后他们轮流进行操作。每次操作时，玩家可以取字符串 $ s $ 的第一个或最后一个字符，将其从 $ s $ 中移除并添加到自己字符串的**最前面**。

当字符串 $ s $ 变为空时游戏结束。拥有字典序较小的字符串的玩家获胜。如果两个玩家的字符串相等，则为平局。

假设爱丽丝和鲍勃都足够聪明，判断谁会获胜，或者游戏是否会平局。

数据组数 $ t \leq 10^3 $，$ \sum|s| \leq 2 \times 10^3 $。保证所有输入的 $ |s| $ 长度都为偶数。

**输入输出格式**：

**输入格式**：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。
- 每个测试用例包含一行，是一个由小写拉丁字母组成的非空字符串 $ s $。字符串 $ s $ 的长度是偶数。
- 所有测试用例的字符串总长度不超过 $ 2000 $。

**输出格式**：
- 对于每个测试用例，如果两位玩家都发挥最佳，输出游戏的结果。如果爱丽丝获胜，打印 "Alice"。如果鲍勃获胜，打印 "Bob"。如果是平局，打印 "Draw"。

**输入输出样例**：

**输入样例 #1**：
```
2
forces
abba
```

**输出样例 #1**：
```
Alice
Draw
```**题目大意**： 爱丽丝和鲍勃在玩一个游戏。游戏开始时，他们得到一个由小写拉丁字母组成的非空字符串 $ s $，字符串的长度是偶数。每位玩家自己也有一个初始为空的字符串。 爱丽丝先开始，然后他们轮流进行操作。每次操作时，玩家可以取字符串 $ s $ 的第一个或最后一个字符，将其从 $ s $ 中移除并添加到自己字符串的**最前面**。 当字符串 $ s $ 变为空时游戏结束。拥有字典序较小的字符串的玩家获胜。如果两个玩家的字符串相等，则为平局。 假设爱丽丝和鲍勃都足够聪明，判断谁会获胜，或者游戏是否会平局。 数据组数 $ t \leq 10^3 $，$ \sum|s| \leq 2 \times 10^3 $。保证所有输入的 $ |s| $ 长度都为偶数。 **输入输出格式**： **输入格式**： - 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。 - 每个测试用例包含一行，是一个由小写拉丁字母组成的非空字符串 $ s $。字符串 $ s $ 的长度是偶数。 - 所有测试用例的字符串总长度不超过 $ 2000 $。 **输出格式**： - 对于每个测试用例，如果两位玩家都发挥最佳，输出游戏的结果。如果爱丽丝获胜，打印 "Alice"。如果鲍勃获胜，打印 "Bob"。如果是平局，打印 "Draw"。 **输入输出样例**： **输入样例 #1**： ``` 2 forces abba ``` **输出样例 #1**： ``` Alice Draw ```