P6495 [COCI 2016/2017 #2] Tavan
题目描述
Željko 正在读奶奶的一封信。由于年代久远，信中的一些单词已经无法辨认。他选出了一个长度为 $n$ 的单词，将其中 $m$ 个无法辨认的字母替换为 `#`。
对于每一处 `#`，奶奶都给出了 $k$ 个字母，该处原先的字母是这 $k$ 个字母之一。所有可能的单词中**按字典序排列**的第 $x$ 个，即为原先的单词。
请你帮助他们找出原先的单词。
输入格式
第一行四个整数 $n,m,k,x$。
第二行一个长度为 $n$ 的字符串，表示 Željko 选出的单词。
接下来 $m$ 行，每行一个长度为 $k$ 的字符串，表示奶奶给出的字母。
输出格式
一行，一个字符串，表示原先的单词。
说明/提示
#### 样例 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T2 Tavan_**。