病毒

题目描述

明文字母表为前m个小写字母a..，m等于给定密文字典中出现的不同字母数。病毒把这m种字母一一替换为m个不同的小写字母，其他字符不参与本题。给定感染后的字典，原字典按通常字典序非降排列；同一单词可重复。根据它恢复最后一串密文字母。只有当全部m种字母的顺序能够唯一确定，才算字典完整。

输入

第一行K，1≤K≤50000；随后K行非空密文单词，每词长度≤1000，单词总长度≤10^6。最后一行非空待恢复串，长度≤10^5，均为小写字母。

输出

若词典字母序约束矛盾、不足以唯一确定全部字母映射，或待恢复串含字典中未出现的字母，输出0；否则输出恢复的明文串。

输入样例

6
cebdbac
cac
ecd
dca
aba
bac
cedab

输出样例

abcde

本地补充约定

明确本地教学的缩减字母表先验（明文为前m个字母、密文可为任意m字母），补输入总量；字典不完整按全m映射不唯一判断，不自行猜测缺失字母。

本题使用独立构造并核验的训练数据，非官方原版数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：明确本地教学的缩减字母表先验（明文为前m个字母、密文可为任意m字母），补输入总量；字典不完整按全m映射不唯一判断，不自行猜测缺失字母。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1396。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。