E - Shiritori

分数：$500$ 分

题目描述

高橋字典中有 $N$ 个词; 第 $i$ 个词是 $s_i$。

使用这个字典，高橋和青木将会进行3-心跳游戏，规则如下：

• 高橋和青木轮流说词，高橋先说。
• 每个玩家必须说一个以前一个词的最后三个字符开始的词。例如，如果一个玩家说 高橋，下一个玩家可以说 船 或 盾牌 等，但不可以说 青木, 唱, 或 他的。
• 区分大小写。例如，一个玩家不能在高橋之后说 船。
• 如果一个玩家没有词可说，则该玩家输掉游戏。
• 玩家不能说字典中没有的词。
• 相同的词可以多次使用。

对于每个 $i$ $(1 \leq i \leq N)$，确定当高橋说出以单词 $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
abcd
bcda
ada

青木
高橋
平局

当高橋开始游戏时说 abcd，青木接下来说 bcda，然后高橋将没有词可说，导致青木赢。因此，应该输出 青木。

当高橋开始游戏时说 bcda，青木将没有词可说，导致高橋赢。因此，应该输出 高橋。

当高橋开始游戏时说 ada，两个玩家都将重复说 ada 永远不停止游戏。因此，应该输出 平局。注意他们可以使用相同的词任意次数。

1
ABC

平局

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

高橋
高橋
高橋
青木
高橋