Reconstructing the Original Word

Željko is reading a letter from his grandmother. Due to the age of the letter, some of the words have become illegible. He selected a word of length (n), and replaced (m) of its letters with the symbol '#' because they could not be deciphered. For each occurrence of '#', his grandmother provided a set of (k) possible letters. All the possible words that can be formed by replacing each '#' with one of its corresponding letters are arranged in lexicographical order. The original word is the (x)-th word in that ordered list.

Your task is to reconstruct the original word.

inputFormat

The first line of input contains four integers (n), (m), (k), and (x) separated by spaces:

• (n): the length of the word.
• (m): the number of unknown letters replaced with '#'.
• (k): the number of possible letters for each unknown position.
• (x): the 1-indexed position of the original word in the lexicographically sorted list of all possible words.

The second line contains a string of length (n) consisting of lowercase letters and character '#' (unknown positions).

The next (m) lines each contain a string of (k) distinct lowercase letters. The (i)-th of these lines corresponds to the possible letters for the (i)-th '#' in the word (from left to right). When constructing the list of possible words, consider the letters for each '#' in lexicographical order.

outputFormat

Output the reconstructed original word.

sample

7 2 3 4
ab#d#fg
cde
xyz

abddxfg