题目描述

Željko 正在读奶奶的一封信。由于年代久远，信中的一些单词已经无法辨认。他选出了一个长度为 $n$ 的单词，将其中 $m$ 个无法辨认的字母替换为 #。

对于每一处 #，奶奶都给出了 $k$ 个字母，该处原先的字母是这 $k$ 个字母之一。所有可能的单词中按字典序排列的第 $x$ 个，即为原先的单词。

请你帮助他们找出原先的单词。

输入格式

第一行四个整数 $n,m,k,x$。

第二行一个长度为 $n$ 的字符串，表示 Željko 选出的单词。

接下来 $m$ 行，每行一个长度为 $k$ 的字符串，表示奶奶给出的字母。

输出格式

一行，一个字符串，表示原先的单词。

9 2 3 7
po#olje#i
sol
znu 

posoljeni

4 1 2 2
#rak
zm 

zrak 

提示

样例 1 解释

所有可能的单词按字典序排列如下：

• pololjeni
• pololjeui
• pololjezi
• poooljeni
• poooljeui
• poooljezi
• posoljeni
• posoljeui
• posoljezi

第 $7$ 个单词为 posoljeni。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 500$，$1\le m\le n$，$1\le k\le 26$，$1\le x\le 10^9$。

所有字符串中仅包含小写字母和 #。

说明

题目译自 COCI2016-2017 CONTEST #2 T2 Tavan。