Problem #3732 - ECNU Online Judge

单点时限: 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 \leq N \leq 500000, 1 \leq M \leq N, 1 \leq K \leq 26, 1 \leq X \leq 10^{18})$ 。

第二行长度为 $N$ 的单词，包含小写字母和 # 。

接下来 $M$ 行，每行包括 $K$ 个字母，表示第 $i$ 个难以辨认的字母可能由这些字母代替。

保证 $X$ 不超过能构造的单词数量。

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

Input

5 2 3 4
c##nb
std
lws

Output

cslnb

478 人解决，702 人已尝试。

556 份提交通过，共有 3659 份提交。

2.8 EMB 奖励。

创建: 5 年，4 月前.

修改: 5 年，4 月前.

最后提交: 1 月前.

来源: N/A

string

3732. 纸条