Problem Description

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

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

For example, using qwertyuiopasdfghjklzxcvbnm as the key to encrypt cezar yields etmqk.

He hopes that, after encrypting all words and sorting them in ascending lexicographical order, the original $a_i$-th word will be in position $i$. Determine whether this can be achieved. If it can, output any feasible key.

Input Format

The first line contains an integer $n$.

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

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

Output Format

This problem uses Special Judge.

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

Otherwise, output DA. Then output one more line with any feasible key.

2
ab
bc
2 1 

DA
bacdefghijklmnopqrstuvwxyz 

3
abc
bcd
add
1 2 3 

NE 

3
bbb
ccc
ddd
2 3 1 

DA
adbcefghijklmnopqrstuvwxyz 

Hint

Sample Explanation

Sample 1 Explanation

Using bacdefghijklmnopqrstuvwxyz as the key, we get:

• ba
• ac

After sorting in ascending lexicographical order, we get:

• ac
• ba

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

Sample 3 Explanation

Using adbcefghijklmnopqrstuvwxyz as the key, we get:

• ddd
• bbb
• ccc

After sorting in ascending lexicographical order, we get:

• bbb
• ddd
• ccc

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

Constraints

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

The length of each word is at most $100$, and each word contains only lowercase letters.

Notes

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

Translated by ChatGPT 5