3414. Mr. Panda and Fantastic Beasts

单点时限: 1.0 sec

内存限制: 256 MB

Mr. Panda loves fantastic beasts, he is going to use a magic spell to figure out where to find them. Given $N$ strings $S_1, S_2, \ldots, S_N$ where $S_i$ only contains lowercase alphabet letters, the magic spell is the shortest string which is only contained in the first string as a substring. If there is at least one solution, output the lexicographically smallest one.

If there is no solution, output Impossible instead.

输入格式

First line contains an integer $N$ $(1 \le N \le 50~000)$ which is the number of strings.

Following is $N$ lines, each line has a non-empty string $S_i$ which only contains lowercase alphabet letters.

The dataset guarantees $N \le |S_1| + |S_2| + \ldots + |S_N| \le 250~000$.

输出格式

Output the answer string or Impossible.

样例

Input
2
aba
bab
Output
aba
Input
3
qnu
cvbb
bnu
Output
q
Input
3
a
aa
aaa
Output
Impossible

4 人解决,4 人已尝试。

9 份提交通过,共有 26 份提交。

7.0 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,11 月前.

最后提交: 1 年,1 月前.

来源: 2016-2017 ACM-ICPC CHINA-Final

题目标签