Mirko 想对 n 个单词进行加密。加密过程是这样的：

1. 选择一个英文字母表的排列作为密钥。
2. 将单词中的 a 替换为密钥中的第一个字母，b 替换为密钥中的第二个字母……以此类推。

例如，以 qwertyuiopasdfghjklzxcvbnm 作为密钥对 cezar 加密后，将得到 etmqk。
他希望，将所有单词加密并按字典序升序排列后，最初的第 a_i 个单词位于第 i 位。
请你判断，这能否实现。如果能，请给出任意一种可行的密钥。

第一行一个整数 n。
接下来 n 行，每行一个字符串，表示待加密的单词。
最后一行 n 个整数，表示 a_i。

如果 Mirko 的要求不能实现，输出 NE。
否则，输出 DA。接下来一行输出任意一种可行的密钥。

样例二：
输入：
3
abc
bcd
add
1 2 3 
输出：
NE
样例三：
输入：
3
bbb
ccc
ddd
2 3 1 
输出：
DA
adbcefghijklmnopqrstuvwxyz 

样例 1 解释

以 bacdefghijklmnopqrstuvwxyz 为密钥加密后，得到：

• ba
• ac

字典序升序排列后，得到：

• ac
• ba

原先的第一个单词在第二位，第二个单词在第一位。符合要求。

样例 3 解释

以 adbcefghijklmnopqrstuvwxyz 为密钥加密后，得到：

• ddd
• bbb
• ccc

字典序升序排列后，得到：

• bbb
• ddd
• ccc

原先的第一个单词在第二位，第二个单词在第三位，第三个单词在第一位。符合要求。

---

数据规模与约定

对于 $100\%$ 的数据，$2\le n\le 100$，1≤ai≤n。

所有单词的长度不超过 $100$，且只包含小写字母。

题目译自 COCI2016-2017 CONTEST #1 T3 Cezar

数据结构 Trie