题目描述

高橋辞書には $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$ $s_1$ $s_2$ $\vdots$ $s_N$

输出格式

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

题目大意

给定 $N$ 个单词，Takahashi 和 Aoki 二人使用这 $N$ 个单词进行成语接龙，二者轮流说出单词，接龙的规则如下：

1. Takahashi 先手， Aoki 后手；
2. 当一个人说出单词后，另一个人必须选择一个单词满足：前一个人说的单词的后三个字母等于此单词的前三个字母，并说出它，如果这个人没有合法的单词可以说出，他输了;
3. 单词可以重复使用，区分大小写。

请你输出先手 Takahashi 从第 $i\ (1\le i\le N)$ 个单词开始说的情况下，且二者都绝顶聪明，游戏的胜负情况。若先手必胜输出 Takahashi，后手必胜输出 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$ 以下の文字列

Sample Explanation 1

高橋君が abcd から始めたとき、次に青木君が bcda と言って高橋君は言う単語がなくなります。よって青木君が勝つので Aoki と出力してください。 高橋君が bcda から始めたとき、次に青木君は言う単語がなくなります。よって高橋君が勝つので Takahashi と出力してください。 高橋君が ada から始めたとき、二人とも ada を繰り返すのでしりとりが終わることはありません。よって Draw と出力してください。同じ単語を何度でも使用できることに注意してください。