Mirko has an array of
We encrypt the text using a substitution cypher by first choosing a key – a permutation of the English alphabet. Then we replace all occurrences of letter a
with the first letter of the key, all occurrences of letter b
with the second letter of the key, and so on until letter z
.
Besides the words, Mirko has an array
Let's recall that the lexicographic word order is the order in which the words appear in the dictionary. If we are comparing two words, going from left to right, we search for the first position in both words where the letters differ and, based on that, we determine which word is lexicographically smaller. If word
Mirko is currently not in the mood for encrypting, so he kindly asks you to do it for him.
Input Specification
The first line of input contains the integer
Each of the following
The last line contains
In test cases worth 30 points total, the words will consist of only the first
Output Specification
In the case when a solution doesn't exist, output NE
.
Otherwise, output DA
in the first line, and in the second line output a word consisting of
If multiple solutions exist, output any.
Sample Input 1
2
ab
bc
2 1
Sample Output 1
DA
bacdefghijklmnopqrstuvwxyz
Explanation for Sample Output 1
After encrypting, the words become ba
, ac
, after lexicographic sorting, the array becomes ac
, ba
, which means the first word ended up in the second spot, and the second word in the first spot.
Sample Input 2
3
abc
bcd
add
1 2 3
Sample Output 2
NE
Sample Input 3
3
bbb
ccc
ddd
2 3 1
Sample Output 3
DA
adbcefghijklmnopqrstuvwxyz
Explanation for Sample Output 3
After encrypting, the words become ddd
, bbb
, ccc
, after lexicographic sorting, the array becomes bbb
, ccc
, ddd
, which means the first word ended up in the third spot, the third word in the second spot, and the second word in the first spot.
Comments