Score : $500$ points

问题描述

高桥词典收录了 $N$ 个单词，其中第 $i$ 个单词 $(1 \leq i \leq N)$ 是 $s_i$。

使用这个词典，高桥和青木将进行一场“3- Shiritori”游戏，规则如下：

• 高桥和青木轮流说出单词，由高桥先开始。
• 每位玩家必须说出一个以前一个单词的最后三个字符开头的单词。例如，如果玩家说出 Takahashi，下一位玩家可以选择说 ship 或 shield 等词，但不能说 Aoki、sing 或 his。
• 大小写有区别。例如，玩家不能在 Takahashi 后面接 ShIp。
• 无法说出单词的玩家判负。
• 玩家不能说出词典中未列出的单词。
• 同一单词可以被多次使用。

对于每个 $i$ $(1 \leq i \leq N)$，假设两位玩家都采取最优策略（即首先避免自己输掉游戏，其次尽可能战胜对手），判断当高桥以单词 $s_i$ 开始游戏时，谁将会获胜。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:23:19