Shiritori

题目描述

Takahashi 字典列出了 $N$ 个单词；第 $i$ 个单词 $(1 \leq i \leq N)$ 为 $s_i$。 使用该字典，Takahashi 和 Aoki 将进行 $3$-shiritori，游戏规则如下。

Takahashi 与 Aoki 轮流说单词，Takahashi 先行。 每位玩家必须说一个以上一位玩家所说单词的最后三个字符为开头的单词。例如，如果某位玩家说了 $Takahashi$，下一位玩家可以说 $ship$ 或 $shield$ 等，但不能说 $Aoki$、$sing$ 或 $his$。 区分大小写。例如，玩家不能在 $Takahashi$ 之后说 $ShIp$。 无法说出符合规则的单词的一方将会输。 玩家不能说字典中没有列出的单词。 同一个单词可以被重复使用多次。

对于每个 $i$ $(1 \leq i \leq N)$，判定当 Takahashi 以单词 $s_i$ 开始游戏时谁会获胜。这里假设双方都进行最优游戏。更具体地说，每位玩家首先优先避免自己失败，其次优先击败对手。

输入格式

输入从标准输入给出，格式如下： $N$ $s_1$ $s_2$ $\vdots$ $s_N$

输出格式

输出 $N$ 行。第 $i$ 行 $(1 \leq i \leq N)$ 应当在 Takahashi 以单词 $s_i$ 开始游戏时输出 $Takahashi$（若 Takahashi 获胜）、$Aoki$（若 Aoki 获胜）或 $Draw$（若该情形下游戏会无休止继续且无人失败）。

3
abcd
bcda
ada

Aoki
Takahashi
Draw

1
ABC

Draw

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

Takahashi
Takahashi
Takahashi
Aoki
Takahashi

提示

$N$ 是一个在 $1$ 到 $2 \times 10^5$（含）之间的整数。 $s_i$ 是一个长度在 $3$ 到 $8$（含）之间、由大小写英文字母组成的字符串。当 Takahashi 以单词 $abcd$ 开始时，Aoki 会接着说 $bcda$，随后 Takahashi 将无法再说单词，导致 Aoki 获胜。因此我们应当输出 $Aoki$。 当 Takahashi 以单词 $bcda$ 开始时，Aoki 将无法说单词，Takahashi 因此获胜。因此我们应当输出 $Takahashi$。 当 Takahashi 以单词 $ada$ 开始时，双方会重复说 $ada$ 并且游戏永远不会结束。因此我们应当输出 $Draw$。注意他们可以任意次数重复使用相同的单词。

标签: AtCoder|abc209E

来源

AtCoder|abc209E