Ancient Language

题意翻译

## 题目描述 在探险一个古老的洞穴时，研究人员发现了一堆来自一本书的杂乱的书页。幸运的是，所有的书页都是完整的并且有着自己的页码。所以，研究人员可以将它复原。 在仔细地研究了一遍这些书页后，语言学家认为这可能是一种字典。有趣的是这个古典文明所使用的字母表是英文字母表的一部分，但不是按英文的顺序来的。 给出研究人员已经找到的书页的有关内容，你的任务是用给出的字典上的有关内容还原这个字母表。 ## 输入格式 第一行两个整数：$n$和$k$ $(1n,k≤10^3)$，分别表示已经找到的书页的页数和每页书上的单词个数； 接下来$n$组： 每组第一行一个整数$p_i$$0≤p_i<10^3$，表示页码； 接下来$k$行每行一个字符串（长度不超过100）表示写在第$p_i$也的单词 ## 输出格式 输出一个字符串表示该字典对应的字母表； 如果这本书不是字典，输出 "IMPOSSIBLE"（不含括号）； 如果有多种答案，请输出任意一种

题目描述

While exploring the old caves, researchers found a book, or more precisely, a stash of mixed pages from a book. Luckily, all of the original pages are present and each page contains its number. Therefore, the researchers can reconstruct the book. After taking a deeper look into the contents of these pages, linguists think that this may be some kind of dictionary. What's interesting is that this ancient civilization used an alphabet which is a subset of the English alphabet, however, the order of these letters in the alphabet is not like the one in the English language. Given the contents of pages that researchers have found, your task is to reconstruct the alphabet of this ancient civilization using the provided pages from the dictionary.

输入输出格式

输入格式

First-line contains two integers: $ n $ and $ k $ ( $ 1 \le n, k \le 10^3 $ ) — the number of pages that scientists have found and the number of words present at each page. Following $ n $ groups contain a line with a single integer $ p_i $ ( $ 0 \le n \lt 10^3 $ ) — the number of $ i $ -th page, as well as $ k $ lines, each line containing one of the strings (up to $ 100 $ characters) written on the page numbered $ p_i $ .

输出格式

Output a string representing the reconstructed alphabet of this ancient civilization. If the book found is not a dictionary, output "IMPOSSIBLE" without quotes. In case there are multiple solutions, output any of them.

输入输出样例

输入样例 #1

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

输出样例 #1

acb