P6286 [COCI 2016/2017 #1] Cezar

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.

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$.

**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.

#### 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T3 Cezar_**。 Translated by ChatGPT 5