B. New String
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given $$$n$$$ strings and a new rule of overload the less-than sign, please print the $$$K$$$-th lexicographically smallest string.

Every string contains only lowercase letters.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • there exists a position $$$i$$$, $$$a_i \lt b_i$$$ and for all $$$j \lt i$$$, $$$a_j=b_j$$$,
  • for every $$$i$$$, $$$a_i=b_i$$$ and the length of $$$a$$$ is less than the length of $$$b$$$.
Input

The first line gives $$$26$$$ characters from $$$a$$$ to $$$z$$$, each character will appear only once. The earlier a letter appears, the smaller it is. For example, $$$acb \cdots xyz$$$ in the first line means that character '$$$c$$$' is less than character '$$$b$$$' and character '$$$c$$$' is greater than character '$$$a$$$'.

The second line contains an integer $$$n$$$ $$$(1 \lt n \lt 10^3)$$$, indicating the number of strings.

Next $$$n$$$ lines, each line contains a string, whose length of the string is less than $$$10^3$$$.

The next line contains an integer $$$K$$$ $$$(1 \leq K \leq n)$$$, indicating the $$$K$$$-th smallest string you need to find.

Output

The $$$K$$$-th lexicographically smallest string.

Examples
Input
acbdefghijklmnopqrstuvwxyz
2
abc
acb
1
Output
acb
Input
zabcdefghijklmnopqrstuvwxy
2
a
b
1
Output
a