← 返回题目列表

AtCoder · abc209_e

E. 知鸟

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

高桥词典列出 N 字;的 i- 第一个字 (1 \leq i \leq N) is s_i.

使用这本词典,高桥和青木将玩 3-shiritori,如下所示。

  • 高桥和青木交替说话,高桥先说。
  • 每个玩家必须说出一个以前一个单词的最后三个字符开头的单词。例如,如果玩家说 Takahashi,下一个玩家可以说 ship or shield 以及其他选择,但不是 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