分数: 500 点
问题陈述
高桥词典列出 N 字;的 i- 第一个字 (1 \leq i \leq N) is s_i.
使用这本词典,高桥和青木将玩 3-shiritori,如下所示。
- 高桥和青木交替说话,高桥先说。
- 每个玩家必须说出一个以前一个单词的最后三个字符开头的单词。例如,如果玩家说
Takahashi,下一个玩家可以说shiporshield以及其他选择,但不是Aoki,sing,或his. - 区分大小写。例如,玩家不能说
ShIp以下Takahashi. - 无法说出一句话的玩家就输了。
- 玩家不能说出字典中未列出的单词。
- 同一单词可以多次使用。
对于每个 i (1 \leq i \leq N),当高桥开始游戏时说出这个词来确定谁会获胜 s_i。在这里,我们假设两名球员都处于最佳状态。更具体地说,每个玩家首先考虑的是避免自己的损失,其次考虑的是击败对手。
约束
- N 是介于 1 和 2 \times 10^5 (含)。
- s_i 是长度介于 3 和 8 (含)由小写和大写英文字母组成。
输入
输入由标准输入按以下格式给出:
N s_1 s_2 \vdots s_N
输出
打印 N 行。的 i第行 (1 \leq i \leq N) 应包含 Takahashi 如果高桥在说这个词开始游戏时获胜 s_i, Aoki 如果青木在这种情况下获胜,并且 Draw 如果游戏永远继续下去,并且在这种情况下他们都没有输。
示例输入 1
3 abcd bcda ada
示例输出 1
Aoki Takahashi Draw
当高桥开始游戏时说 abcd,青木会说 bcda 接下来,高桥将无话可说,导致青木获胜。因此,我们应该打印 Aoki.
当高桥开始游戏时说 bcda,青木无话可说,导致高桥获胜。因此,我们应该打印 Takahashi.
当高桥开始游戏时说 ada,两位玩家都会重复 ada 并且永远不会结束游戏。因此,我们应该打印 Draw。请注意,他们可以多次使用同一个单词。
示例输入 2
1 ABC
示例输出 2
Draw
示例输入 3
5 eaaaabaa eaaaacaa daaaaaaa eaaaadaa daaaafaa
示例输出 3
Takahashi Takahashi Takahashi Aoki Takahashi