D :: Dictionary attack

Time Limit: 2 Seconds    Memory Limit: 65536 KB

You are performing a dictionary attack to hack an unfortunate user’s account. You have a list of n potential words that the user is most likely to use. This list is prefix free, i.e. no word in the list is a prefix of another. You guess that the password is concatenation of one or more words of the list without any delimiters. 

The average person usually uses passwords that have the following criteria:

• The number of words used in password is limited as the users can memorize only a few number words. Depending on the number of words in your dictionary, you assume the number of words used in a password is at most m. If a word is used multiple times, all occurrences of that word are taken into account.
• Users are reluctant to use long passwords as they are error prone to type. So the length of a password is at most L.

You are setting up a program to run over all passwords one by one in lexicographical order. But even for computers it takes days to check all possible combinations. Especially if you setup a time interval between two consecutive queries to prevent system administrators become suspicious.

The program you have written gives an index k in the input, and starts its work from the k-th lexicographically smallest word. In each run, the program iterates over possible words in search space until it finds the password. If it fails to identify the credentials for 12 hours, it exits. The only thing it reports is the index of last checked word.

You noted that the program is inefficient when the input argument gets large. You want to optimize it. Your task is to find the k-th smallest possible password with a quick algorithm.

Input

First line of input contains a single integer t (t ≤ 100), the number of tests that follow. The first line of each test contains four space separated integers n, m, L, k (1 ≤ n ≤ 1000,1 ≤ m ≤ 10,1 ≤ L ≤ 1000,1 ≤ k ≤ 10⁹), the number of words in the dictionary, maximum number of words used in a password, maximum length of a password and the index of the password in the sorted list of all  possible combinations that you are looking for.

Each of the next n lines contains a string of length at most 300. Words consist of only lowercase Latin letters. It is guaranteed that no word in the list is a prefix of another.

Output

For each test you should output a single line, the k-th lexicographically smallest possible password. If the total number of possible password is less than k, you should print "empty" instead.

Sample Input

6
2 2 11 1
simple
sample
2 2 11 2
simple
sample
2 2 12 2
simple
sample
2 2 11 3
simple
sample
2 2 12 7
simple
sample
4 4 10 17
zart
jamshid
pmp
happy

Sample Output

sample
simple
samplesample
empty
empty
zartpmp

Submit

Source: 4th Kashan University's ACM Contest