Problem Description

Mirko wants to encrypt $n$ words. The encryption process is as follows:

1. Choose a permutation of the English alphabet as the key.
2. Replace a with the first letter of the key, b with the second letter of the key, and so on.

For example, using qwertyuiopasdfghjklzxcvbnm as the key to encrypt cezar will result in etmqk.

He wants the $a_i$-th word, after being encrypted and sorted lexicographically, to be in the $i$-th position. Determine if this is possible. If it is, provide any one feasible key.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain a string, representing the words to be encrypted.

The last line contains $n$ integers, representing $a_i$.

Output Format

This problem uses a Special Judge.

If Mirko's requirement cannot be met, output NE.

Otherwise, output DA. The next line should contain any one feasible key.

Sample Input and Output

Sample Input #1

2
ab
bc
2 1 

Sample Output #1

DA
bacdefghijklmnopqrstuvwxyz 

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 

Notes

Sample Explanation

Sample 1 Explanation

Using bacdefghijklmnopqrstuvwxyz as the key, the encrypted words are:

• ba
• ac

After sorting lexicographically, we get:

• ac
• ba

The original first word is in the second position, and the second word is in the first position. This meets the requirement.

Sample 3 Explanation

Using adbcefghijklmnopqrstuvwxyz as the key, the encrypted words are:

• ddd
• bbb
• ccc

After sorting lexicographically, we get:

• bbb
• ddd
• ccc

The original first word is in the second position, the second word is in the third position, and the third word is in the first position. This meets the requirement.

Data Size and Constraints

For $100\%$ of the data, $2 \le n \le 100$, and $1 \leq a_i \leq n$.

The length of all words does not exceed $100$ and only contains lowercase letters.

Notes

This problem is translated from COCI2016-2017 CONTEST #1 T3 Cezar.

见题面 Input 部分

见题面 Output 部分