单词游戏（A Word Game）

题目背景

Joe 和 Mary 喜欢玩一种接龙式的猜词游戏。两人掌握完全相同的一份词表，但在游戏过程中，他们不会直接说出完整的单词，而是轮流把当前的字母前缀延长一位。

谁先无意中说出了词表中的一个完整单词，谁就立即输掉游戏。两人都足够聪明，会按照最有利于自己的方式行动；当若干种行动效果完全相同时，他们还会优先选择字典序较小的字母。

给定两人共同掌握的词表，请判断在双方均采用最优策略时，最后导致失败的完整单词是什么。

题目描述

游戏由两名玩家进行，第一名玩家先手，第二名玩家后手。

开始时，当前前缀为空串。每一回合，当前玩家需要在前缀末尾添加一个小写英文字母，使得新的前缀仍然是词表中至少一个单词的前缀。

例如，若词表中存在单词 program 和 programmer，当前前缀为 pro，则玩家可以选择字母 g，将前缀变为 prog。

当某位玩家添加一个字母后，当前前缀恰好等于词表中的某个完整单词时，该玩家立即输掉游戏，游戏结束。

需要特别注意：即使当前前缀还是其他更长单词的前缀，只要它本身已经是一个完整单词，游戏也会立即结束。例如，若 fir 和 fire 都在词表中，当某位玩家说出 fir 时，他会立刻输掉，不能继续延长为 fire。

两名玩家都采用完美策略：

• 如果当前玩家存在必胜策略，他会选择能够使自己获胜且让游戏尽快结束的行动；
• 如果当前玩家无论如何都会失败，他会选择能够让自己尽可能晚失败的行动；
• 若多个可选字母在胜负结果和游戏结束时间上完全相同，则选择字典序最小的字母。

游戏的结果定义为：输掉游戏的玩家最后说出的完整单词。

请输出双方均采用完美策略时的游戏结果。

输入格式

第一行包含一个整数 $n$，表示接下来输入的字符串行数。

接下来 $n$ 行，每行包含一个或多个由单个空格分隔的单词。这些行中的所有单词共同构成双方掌握的词表。

输出格式

输出一个字符串，表示双方均采用完美策略时，输掉游戏的玩家最后说出的完整单词。

数据范围

对于所有测试数据：

• $1\le n\le 50$；
• 接下来的每一行长度均在 $1$ 到 $50$ 之间；
• 每一行由一个或多个小写英文字母组成的单词构成，相邻单词之间恰好有一个空格；
• 每个单词的长度均在 $1$ 到 $20$ 之间；
• 词表中不存在两个完全相同的单词；
• 每一行没有前导空格或尾随空格。

样例 1

输入

2
pascal program programmer task tree
treacherous treachery tread trace

输出

treacherous

解释

先手第一步只能选择 p 或 t。

若先手选择 p，后手可以选择 r，之后先手最终会被迫说出 program 并失败。

若先手选择 t，无论之后如何行动，先手最终仍会失败。按照“无法获胜时尽量延迟失败”的原则，最晚结束的路径会到达 treacherous，因此输出该单词。

样例 2

输入

2
pascal programmer task tree
treacherous treachery tread trace

输出

programmer

解释

与样例 1 相比，词表中删除了 program。

此时先手以 p 开头可以获胜。后手在必败的情况下，会选择让失败尽量晚发生的分支，因此最终单词为较长的 programmer。

样例 3

输入

7
academic
base
board
cola
code
cute
hack

输出

code

解释

若先手选择 b，他最终会失败；选择其他首字母则可以获胜。

在所有最快获胜的方案中，以 c 和 h 开头均可达到相同效果，因此先手选择字典序较小的 c。后续同样按照字典序最小原则选择，最终失败单词为 code。