P6495 [COCI 2016/2017 #2] Tavan

Željko is reading a letter from his grandma. Because it is very old, some words in the letter can no longer be recognized. He picked a word of length $n$ and replaced $m$ unrecognizable letters with `#`. For each `#`, grandma provided $k$ letters, and the original letter at that position is one of these $k$ letters. Among all possible words, the $x$-th one **in lexicographical order** is the original word. Please help them find the original word.

The first line contains four integers $n,m,k,x$. The second line contains a string of length $n$, representing the word Željko picked. The next $m$ lines each contain a string of length $k$, representing the letters provided by grandma.

One line containing a string, representing the original word.

#### Sample 1 Explanation All possible words in lexicographical order are: - `pololjeni` - `pololjeui` - `pololjezi` - `poooljeni` - `poooljeui` - `poooljezi` - `posoljeni` - `posoljeui` - `posoljezi` The $7$-th word is `posoljeni`。 ------------ #### Constraints For $100\%$ of the testdata, $1\le n\le 500$, $1\le m\le n$, $1\le k\le 26$, $1\le x\le 10^9$. All strings contain only lowercase letters and `#`。 ------------ #### Notes **This problem is translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T2 Tavan_**。 Translated by ChatGPT 5