单点时限: 2.0 sec
内存限制: 256 MB
“欢迎您乘坐东方航空公司航班 MU5692 由银川前往上海......”
“我们的飞机很快就要起飞了，请收起小桌板，摘下耳机......”
收起了小桌板，摘下了耳机，Cuber QQ 突然无所事事了。
放耳机进书包的时候，Cuber QQ 无意带出了一些小纸条。是以前的回忆。
纸条在书包中已经存在了不知道多久。水渍泛黄了纸张，有些字他不能认出来。
具体来说，信件是一个包含 $N$ 个字母的单词。其中有 $M$ 个难以辨认的字母，用字符 # 代替。
Cuber QQ 用残存的回忆给对每个难以辨认的字母都给出了 $K$ 个不同的候选字母。
为了方便比较哪个更接近于自己的回忆，Cuber QQ 在纸上列出了所有可能的单词。
在看过这些单词以后，Cuber QQ 认为按照字典序排名，第 $X$ 个单词就是原来的单词。
你能知道 Cuber QQ 以前写了什么吗？
第一行整数 $N,M,K$ 和 $X$ $(1 \le N \le 500000, 1 \le M \le N, 1 \le K \le 26, 1 \le X \le 10^{18})$ 。
第二行长度为 $N$ 的单词，包含小写字母和 # 。
接下来 $M$ 行，每行包括 $K$ 个字母，表示第 $i$ 个难以辨认的字母可能由这些字母代替。
保证 $X$ 不超过能构造的单词数量。
一行一个字符串，表示答案。
5 2 3 4 c##nb std lws
cslnb