/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋辞書には N 個の単語が載っており、i\, (1 \leq i \leq N) 番目の単語は s_i です。
高橋君と青木君は高橋辞書を使って 3 しりとりをします。 3 しりとりのルールは以下です。
- 高橋君と青木君は、高橋君から始めて交互に単語を言い合っていく。
- 各プレーヤーは前の人が言った単語の最後の 3 文字で始まる単語を言わなければならない。例えば、前の人が
Takahashiと言った場合、次の人はship、shieldなどを言うことができ、Aoki、sing、hisなどを言うことはできない。 - 大文字と小文字は区別される。例えば、
TakahashiのあとにShIpを言うことはできない。 - 言う単語がなくなった方が負ける。
- 高橋辞書に載っていない単語を言うことはできない。
- 同じ単語は何度でも使ってよい。
各 i\, (1 \leq i \leq N) について、高橋君が 3 しりとりを単語 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) 行目には、高橋君が 3 しりとりを単語 s_i から始めたとき、高橋君が勝つなら Takahashi、青木君が勝つなら 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
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 sayshiporshieldalong with other choices, but notAoki,sing, orhis. - Uppercase and lowercase are distinguished. For example, a player cannot say
ShIpfollowingTakahashi. - 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