Champion Permutation

In a certain ICPC Regional contest, the ranking was decided by team names in lexicographical order. However, since teams whose names start with the letter \(z\) (and in general, certain positions in the ordering) can be systematically disadvantaged, the organizers decided to use a random permutation of the 26 lowercase English letters to define a new lexicographical order. There are \(26!\) possible permutations. In this contest, there are \(N\) teams, and every team’s name consists only of lowercase letters.

Etna tried to enumerate all \(26!\) permutations in hopes of finding one permutation that would allow each team to become champion (i.e. be ranked first). After her program ran indefinitely, she came to you for help. For each team, your task is to construct a permutation of the 26 letters such that when all teams are sorted according to the lexicographical order induced by that permutation, the given team appears first.

Note: When comparing two strings in any lexicographical order, if one string is a prefix of the other then the shorter string is always considered smaller. Therefore, if for a target team there exists another team whose name is a prefix of the target team’s name, it is impossible to construct any permutation that makes the target team champion. In such cases, output impossible.

For two different team names A (the target team) and B, if they differ at the first position \(i\) (i.e. \(A[i] \neq B[i]\)), then in order for A to dominate B under the new ordering, the letter \(A[i]\) must appear before the letter \(B[i]</em> in the permutation. Your task is to find one valid permutation that satisfies all such constraints for the chosen target team, or determine that no valid permutation exists.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)) representing the number of teams. Each of the following \(N\) lines contains a non-empty string of lowercase English letters representing a team name.

outputFormat

Output \(N\) lines. The \(i\)th line should contain a permutation of the 26 lowercase letters if it is possible to construct one so that the \(i\)th team becomes champion (i.e. it is lexicographically smallest under the permutation induced order), otherwise output impossible.

sample

3
team
code
acid

permutation1\npermutation2\npermutation3