重要信件

题目描述

兔警官朱迪和狐狸尼克得到了一封重要信件，其中原本写着一个长度为 $N$ 的单词。但由于信件被水打湿，其中有 $M$ 个字母已经无法辨认，于是尼克把这些无法辨认的位置统一记为字符 #。

对于每一个 # 位置，朱迪都给出了 $K$ 种可能的字母。于是可以构造出许多可能的原单词。大先生告诉他们，真正的原单词恰好是将这些可能单词按字典序排序后得到的第 $X$ 个单词。请你输出这个单词。

数据范围

• $1 \le N \le 500$
• $1 \le M \le N$
• $1 \le K \le 26$
• $1 \le X \le 10^9$
• 保证 $X$ 不超过所有可构造单词的总数

输入格式

从标准输入按以下格式读取数据：

$N$ $M$ $K$ $X$

$S$

$T_1$

$T_2$

$\vdots$

$T_M$

其中：

• 第一行输入四个整数 $N,M,K,X$。
• 第二行输入一个长度为 $N$ 的字符串 $S$，它只由小写字母和字符 # 组成，并且其中恰好有 $M$ 个 #。
• 接下来 $M$ 行，每行输入一个长度为 $K$ 的字符串，其中第 $i$ 行表示原单词中第 $i$ 个 # 位置可能对应的 $K$ 个字母。

输出格式

输出一行一个字符串，表示按字典序排序后的第 $X$ 个可能单词。

样例

9 2 3 7
po#olje#i
sol
znu

posoljeni

4 1 2 2
#rak
zm

zrak