Problem #3414 - ECNU Online Judge

单点时限: 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}, \dots, 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 \leq N \leq 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 \leq | S_{1} | + | S_{2} | + \dots + | S_{N} | \leq 250 000$ .

输出格式

Output the answer string or Impossible.

样例

Input

2
aba
bab

Output

aba

Input

3
qnu
cvbb
bnu

Output

Input

3
a
aa
aaa

Output

Impossible

4 人解决，6 人已尝试。

9 份提交通过，共有 33 份提交。

7.8 EMB 奖励。

创建: 7 年，6 月前.

修改: 7 年，6 月前.

最后提交: 2 年，1 月前.

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

string

3414. Mr. Panda and Fantastic Beasts

输入格式

输出格式

样例

服务

开源

关于我们