You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

例如，以 qwertyuiopasdfghjklzxcvbnm 作为密钥对 cezar 加密后，将得到 etmqk。

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

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个字符串，表示待加密的单词。

最后一行 $n$ 个整数，表示 $a_i$。

输出格式

本题使用 Special Judge。

如果 Mirko 的要求不能实现，输出 NE。

否则，输出 DA。接下来一行输出任意一种可行的密钥。

2
ab
bc
2 1 

DA
bacdefghijklmnopqrstuvwxyz 

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 \leq a_i \leq n$。

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

说明

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