← 返回题目列表

Codeforces · 510/C

C. 狐狸和名字

中文机器翻译题面 查看原题

Fox Ciel 将发表一篇关于 FOCS(Foxes Operated Computer Systems,发音:“Fox”)的论文。她听到一个传言:论文上的作者名单总是按照字典顺序排列的。

在检查了一些例子后,她发现有时情况并非如此。在某些论文中,作者的姓名并未按正常意义上的字典顺序排序。但确实,在对字母表中的字母顺序进行一些修改之后,作者的顺序就变成了字典顺序!

她想知道拉丁字母表中是否存在字母顺序,使得她提交的论文上的名字按照字典顺序排列。如果是这样,您应该找出任何此类订单。

词典顺序按以下方式定义。当我们比较 s 和 t 时,首先我们找到最左边具有不同字符的位置:si ≠ ti。如果没有这样的位置(即 s 是 t 的前缀,反之亦然),则最短的字符串会更少。否则,我们根据字符 si 和 ti 在字母表中的顺序进行比较。

输入

第一行包含一个整数n (1 ≤ n ≤ 100):姓名数量。

以下 n 行中的每一行都包含一个字符串 namei (1 ≤ |namei| ≤ 100),即第 i 个名称。每个名称仅包含小写拉丁字母。所有的名字都不同。

输出

如果存在给定名称按字典顺序排序的字母顺序,则输出任何此类顺序作为字符“a”–“z”的排列(即首先输出修改后的字母表的第一个字母,然后输出第二个字母,依此类推)。

否则输出一个单词“Impossible”(不带引号)。

示例

输入 #1

3
rivest
shamir
adleman

输出 #1

bcdefghijklmnopqrsatuvwxyz

输入 #2

10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer

输出 #2

Impossible

输入 #3

10
petr
egor
endagorion
feferivan
ilovetanyaromanova
kostka
dmitriyh
maratsnowbear
bredorjaguarturnik
cgyforever

输出 #3

aghjlnopefikdmbcqrstuvwxyz

输入#4

7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck

输出#4

acbdefhijklmnogpqrstuvwxyz