Description

Ž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.

Input Format

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.

Output Format

One line containing a string, representing the original word.

9 2 3 7
po#olje#i
sol
znu 

posoljeni

4 1 2 2
#rak
zm 

zrak 

Hint

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 CONTEST #2 T2 Tavan。

Translated by ChatGPT 5