Kth Sentence

Time limit3sMemory limit512 MB

Summary

Given n distinct words and a length m, print the K-th lexicographically smallest sentence of exactly m letters formed by concatenating the words, or print - if none exists.

Level: Medium7 of 10
Topics: Dynamic programming, Trie, String
Solved: No attempts yet

Problem

A student, Kita_masa, is taking an English exam. In this exam, he has to write a sentence of length $m$ .

He has completely forgotten English grammar, so he decides to consider every sentence of length $m$ that can be built by concatenating the words he knows. He sorts these candidates in lexicographic order and writes the $K$ -th one. He believes it must be the correct sentence because $K$ is today's lucky number.

Each word may be used multiple times, or not at all. The sentence has no extra characters between words. Two sentences are different if their word order differs, even when the concatenated strings are the same.

Input

The first line contains three integers $n$ , $m$ , and $K$ ( $1 \leq n \leq 100$ , $1 \leq m \leq 2000$ , $1 \leq K \leq 10^{18}$ ), separated by spaces. Each of the next $n$ lines contains one word that Kita_masa knows. Each word has a length from 1 to 200 and contains only lowercase letters. All words are distinct.

Output

Print the $K$ -th (1-based) sentence of length $m$ in lexicographic order. If no such sentence exists, print "-".

Examples3

Example 1
Input
```
2 10 2
hello
world
```
Expected output
```
helloworld
```
Example 2
Input
```
3 3 6
a
aa
b
```
Expected output
```
aba
```
Example 3
Input
```
2 59 1000000000000000000
a
b
```
Expected output
```
-
```