102094: [AtCoder]ABC209 E - Shiritori

Problem Statement

The Takahashi Dictionary lists $N$ words; the $i$-th word $(1 \leq i \leq N)$ is $s_i$.

Using this dictionary, Takahashi and Aoki will play $3$-shiritori, which goes as follows.

• Takahashi and Aoki alternately say words, with Takahashi going first.
• Each player must say a word beginning with the last three characters of the previous word. For example, if a player says Takahashi, the next player can say ship or shield along with other choices, but not Aoki, sing, or his.
• Uppercase and lowercase are distinguished. For example, a player cannot say ShIp following Takahashi.
• A player who becomes unable to say a word loses.
• A player cannot say a word not listed in the dictionary.
• The same word can be used multiple times.

For each $i$ $(1 \leq i \leq N)$, determine who will win when Takahashi starts the game by saying the word $s_i$. Here, we assume that both players play optimally. More specifically, each player gives first priority to avoiding his loss and second priority to defeating the opponent.

Constraints

• $N$ is an integer between $1$ and $2 \times 10^5$ (inclusive).
• $s_i$ is a string of length between $3$ and $8$ (inclusive) consisting of lowercase and uppercase English letters.

Input

Input is given from Standard Input in the following format:

$N$
$s_1$
$s_2$
$\vdots$
$s_N$

Output

Print $N$ lines. The $i$-th line $(1 \leq i \leq N)$ should contain Takahashi if Takahashi wins when Takahashi starts the game by saying the word $s_i$, Aoki if Aoki wins in that scenario, and Draw if the game continues forever with neither of them losing in that scenario.

Sample Input 1

3
abcd
bcda
ada

Sample Output 1

Aoki
Takahashi
Draw

When Takahashi starts the game by saying abcd, Aoki will say bcda next, and Takahashi will then have no word to say, resulting in Aoki's win. Thus, we should print Aoki.

When Takahashi starts the game by saying bcda, Aoki will have no word to say, resulting in Takahashi win. Thus, we should print Takahashi.

When Takahashi starts the game by saying ada, both players will repeat ada and never end the game. Thus, we should print Draw. Note that they can use the same word any number of times.

Sample Input 2

1
ABC

Sample Output 2

Draw

Sample Input 3

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

Sample Output 3

Takahashi
Takahashi
Takahashi
Aoki
Takahashi

问题描述

高桥字典中列出了 $N$ 个单词，第 $i$ 个单词 $(1 \leq i \leq N)$ 为 $s_i$。

高桥和青木将使用这个字典玩 3 字头接龙 游戏，规则如下：

• 高桥和青木交替说出单词，由高桥先开始。
• 每个玩家必须说出一个以前一个单词的最后三个字符开头的单词。例如，如果玩家说 Takahashi，下一个玩家可以说 ship 或 shield 等，但不能说 Aoki，sing 或 his。
• 区分大小写。例如，玩家不能在 Takahashi 之后说 ShIp。
• 无法说出单词的玩家输掉游戏。
• 玩家不能说出字典中未列出的单词。
• 同一个单词可以多次使用。

对于每个 $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