409761: GYM103736 B New String

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. New Stringtime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard 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 < b_i$$$ and for all $$$j<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 < n < 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.

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

加入题单

上一题 下一题 算法标签: