#abc209e. [abc209_e]Shiritori

[abc209_e]Shiritori

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

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

请你输出先手 Takahashi 从第 i (1iN)i\ (1\le i\le N) 个单词开始说的情况下,且二者都绝顶聪明,游戏的胜负情况。若先手必胜输出 Takahashi,后手必胜输出 Aoki,平局输出 Draw