#K42507. Alien Dictionary Order

    ID: 27102 Type: Default 1000ms 256MiB

Alien Dictionary Order

Alien Dictionary Order

In this problem, you are given a sequence of words sorted lexicographically according to an unknown (alien) alphabet. Your task is to deduce the correct order of the characters in this alien alphabet.

Formally, let (\mathcal{A}) be the set of characters used by the alien language. The ordering must satisfy that for every directed edge (u \to v) in the precedence graph (derived from adjacent words), the position of (u) is less than the position of (v):
[ \forall (u \to v), \ \text{pos}(u) < \text{pos}(v) ]

If the order cannot be determined (either due to a cycle or because a word is a prefix of a previous word), output Impossible.

inputFormat

The input is read from standard input. The first line contains an integer (n) representing the number of words. This is followed by (n) lines, each containing a non-empty string which is a word in the alien language.

outputFormat

Output to standard output a single line containing a string that represents the ordered sequence of characters according to the alien alphabet. If it is impossible to determine such an order, output Impossible.## sample

5
wrt
wrf
er
ett
rftt
wertf