3732. 纸条

单点时限: 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$ 不超过能构造的单词数量。

输出格式

一行一个字符串,表示答案。

样例

Input
5 2 3 4
c##nb
std
lws
Output
cslnb

424 人解决,636 人已尝试。

483 份提交通过,共有 3298 份提交。

3.0 EMB 奖励。

创建: 10 月前.

修改: 9 月,4 周前.

最后提交: 1 周,1 天前.

来源: N/A

题目标签