重要信件

题目描述:

兔警官朱迪和狐狸尼克终于搞定了那难缠的小恶魔，大先生(黑帮头目小鼩鼱)也兑现了他的承诺。把他知道的动物们被困的线索信息的信件给了朱迪和尼克。

朱迪急忙打开信件，寻找新的线索信息。可是由于不小心信件掉到了水里，狐狸尼克马上把信件捞了上来。

这封信是一个长度为 N 的单词。不幸的是，由于信件刚才掉水里导致有些字母已经无法辨认。机智的狐狸尼克立马拿出一张纸，把这个单词重新写一次，无法辨认的 M 个字母用 '#' 字符替换了。紧接着尼克把这张纸交给了朱迪，朱迪对每个无法辨认的字母给出了 K 种可能。之后，尼克在笔记本上写出了所有可能的单词，为了确定原文中到底是哪个单词，朱迪和尼克决定仔细查找每个单词的属性。

大先生看到笔记本上的这些单词，突然发现，朱迪和尼克要找的这个单词正是对这些单词进行字母顺序排序后的第 X 个单词。聪明的狐狸尼克很快就找到了那个单词，于是立马就和兔警官朱迪去解救那些被关押的动物们了。 

输入格式:

第一行包含整数 N, M, K 和 X。

第二行包含一个长度为 N 的单词，即被朱迪掉水里导致有些字母无法辨认的那个单词(由英文小写字母和字符 '#' 组成，数据保证这个单词中含有 M 个 '#' 字符)。

接下来的 M 行，每行包含一个长度为 K 的单词，这些单词中的第 i 个单词表示待识别单词中第 i 个'#' 字符有可能的字母。

数据保证数字 X 将始终小于或等于可构建的单词总数。 

输出格式:

输出共一行一个单词，即按字母顺序排序后的第 X 个单词。

数据范围:

对于100%的数据：1≤ N ≤ 500；1 ≤ M ≤ N；1 ≤ K ≤ 26；1 ≤ X ≤ 109。

测试点编号 N M K X
1~2  N≤10    M=1   K=3   X≤2
3~4   N≤100 M≤5 K ≤ 8 X≤3×104
5~7    N≤200 M≤10  K≤10 X≤107
8~10  N≤500  M≤N   K≤26   X≤109 

样例输入:

样例1：
9 2 3 7
po#olje#i
sol
znu

样例2：
4 1 2 2
#rak
zm

样例输出:

样例1：
posoljeni

样例2：
zrak

提示:

【样例1解释】 按字母顺序排序后，这些单词如下图所示。

序号    单词
1    pololjeni
2    pololjeui
3    pololjezi
4    poooljeni
5    poooljeui
6    poooljezi
7    posoljeni
8    posoljeui
9    posoljezi 

时间限制: 1000ms
空间限制: 256MB

来源: 温州市计算机学会2023比赛