字母排序问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

G教授是XOI的负责人,有一天他竟然发现自己的计算机染上了一种不常见的病毒。这种病毒的名字叫做ALPHABETVIRUS,当它发作的时候,会将字母用其他的字母代替,但不会将单词的顺序交换。

病毒将计算机中的所有文档都作了相对应的改变。很幸运,G教授的计算机上有一个字典,而我们都知道字典单词是按字母顺序排列的,当然,这个字典也被病毒改变了。因此,要利用字典原来的有序性,找到病毒替换字母的规律,再用以恢复其他文档。由于XOI不能缺少G教授的文件,所以文档必须恢复。但是由于G教授有其他更重要的工作完成,所以他希望你可以帮助他恢复文档,使得XOI的工作可以继续。

G教授会提供感染病毒后的字典和他希望你帮助恢复的字母组。

Input

第一行是两个整数A(<=26)和K(<=50000),A表示需要恢复的字母个数,K表示字典里与这几个字母有关系的单词个数,他们之间用一个空格隔开。接下的K行按原来的字典顺序给出这K个单词。第K+1行是要你恢复的字母组,字母为小写字母。

Output

将字母组输出,如果不可将字母区分,则输出0。

Sample Input

5 6
cebdbac
cac
ecd
dca
aba
bac
cedab

Sample Output

abcde

Hint

Source