Contest Duration: - (local time) (100 minutes) Back to Home
E - Shiritori /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 高橋君と青木君は、高橋君から始めて交互に単語を言い合っていく。
• 各プレーヤーは前の人が言った単語の最後の 3 文字で始まる単語を言わなければならない。例えば、前の人が Takahashi と言った場合、次の人は shipshield などを言うことができ、Aokisinghis などを言うことはできない。
• 大文字と小文字は区別される。例えば、Takahashi のあとに ShIp を言うことはできない。
• 言う単語がなくなった方が負ける。
• 高橋辞書に載っていない単語を言うことはできない。
• 同じ単語は何度でも使ってよい。

i\, (1 \leq i \leq N) について、高橋君が 3 しりとりを単語 s_i から始めたときどちらが勝つかを判定してください。ただし、二人とも最善に行動するとします。具体的には、自分が負けないことを最優先し、その次に相手を負かすことを優先します。

### 制約

• N1 以上 2 \times 10^5 以下の整数
• s_i は英小文字と英大文字のみからなる長さ 3 以上 8 以下の文字列

### 入力

N
s_1
s_2
\vdots
s_N


### 出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、高橋君が 3 しりとりを単語 s_i から始めたとき、高橋君が勝つなら Takahashi、青木君が勝つなら Aoki、しりとりが永遠に続き勝敗が決まらないなら Draw と出力せよ。

### 入力例 1

3
abcd
bcda


### 出力例 1

Aoki
Takahashi
Draw


### 入力例 2

1
ABC


### 出力例 2

Draw


### 入力例 3

5
eaaaabaa
eaaaacaa
daaaaaaa
daaaafaa


### 出力例 3

Takahashi
Takahashi
Takahashi
Aoki
Takahashi


Score : 500 points

### 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


### 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
daaaafaa


### Sample Output 3

Takahashi
Takahashi
Takahashi
Aoki
Takahashi