← 返回题目列表

Codeforces · 1424/M

M. 古代语言

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

在探索古老的洞穴时,研究人员发现了一本书,或者更准确地说,是一本书中的一堆混合页面。幸运的是,所有原始页面都存在,并且每页都包含其编号。因此,研究人员可以重建这本书。

在深入研究这些页面的内容后,语言学家认为这可能是某种词典。有趣的是,这个古老文明使用的字母表是英语字母表的一个子集,然而,这些字母在字母表中的顺序与英语中的顺序不同。

鉴于研究人员找到的页面内容,您的任务是使用词典中提供的页面重建这个古代文明的字母表。

输入

第一行包含两个整数:$$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^3$$$) — 科学家已找到的页数以及每页中出现的单词数。以下 $$$n$$$ 组包含一行,其中包含单个整数 $$$p_i$$$ ($$$0 \le n \lt 10^3$$$) — 第 $$$i$$$ 页的页数,以及 $$$k$$$ 行,每行包含写在编号为 $$$p_i$$$ 的页上的字符串之一(最多 $$$100$$$ 个字符)。

输出

输出一个字符串,代表这个古老文明的重建字母表。如果找到的书不是字典,则输出“IMPOSSIBLE”,不带引号。如果有多个解,则输出其中任意一个。

示例

输入 #1

3 3
2
b
b
bbac
0
a
aca
acba
1
ab
c
ccb

输出 #1

acb