Encrypted Word Ordering

Mirko wants to encrypt n words using a substitution cipher. The encryption is performed as follows:

1. Choose a permutation of the English alphabet as the encryption key.
2. Replace each letter: 'a' is replaced by the first character of the key, 'b' by the second, and so on.

For instance, if the key is qwertyuiopasdfghjklzxcvbnm then the word cezar is encrypted as etmqk.

After encrypting all words, Mirko sorts the encrypted words in lexicographical order (ascending). He requires that the word originally at position \(a_i\) (1-indexed) appears in the \(i\)th position in the sorted order. Your task is to determine if such an encryption key exists, and if it does, output any valid key.

More formally, let the original words be \(w_1, w_2, \dots, w_n\). Let \(f\) be the substitution defined by a permutation key of the 26 lowercase letters. The encrypted word for \(w\) is obtained by applying \(f\) to each character in \(w\). After encrypting all words, let the sorted order be: \[ f(w_{a_1}) \le f(w_{a_2}) \le \dots \le f(w_{a_n}). \] For each adjacent pair (where the comparison is done lexicographically, and when one word is a prefix of another the shorter word is considered smaller), the ordering must hold. Determine if such a key exists, and if so, provide one. In case no valid key exists, output impossible.

Note: When comparing two encrypted words, find the first position where they differ. If none exists and one word is longer than the other, then the shorter word should come first.

inputFormat

The input consists of the following:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of words.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), a permutation of \(\{1, 2, \dots, n\}\). This indicates that after encrypting and sorting the words in lexicographical order, the word originally at position \(a_i\) should become the \(i\)th word.
• The following \(n\) lines each contain a non-empty string consisting only of lowercase English letters, representing the words.

outputFormat

If a valid encryption key exists, output a single line containing a permutation of the 26 lowercase English letters. This key defines the substitution such that the encryption followed by sorting places the word originally at \(a_i\) at the \(i\)th position. If no such key exists, output impossible.

sample

3
2 3 1
abc
bcd
acd

cbadefghijklmnopqrstuvwxyz