Find the K-th Smallest Word

You are given a list of n unique words and an integer k. Your task is to determine the k-th smallest word in lexicographical (alphabetical) order. In other words, if all words are sorted in ascending alphabetical order, you need to output the word in the k-th position.

The problem makes use of the lexicographical comparison defined as follows:

\( \text{compare}(word_1, word_2) = \begin{cases} -1, & \text{if } word_1 word_2 \end{cases} \)

Note: You must read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input consists of multiple lines:

1. The first line contains an integer n, the number of words.
2. The second line contains n space-separated words.
3. The third line contains an integer k representing which smallest word to find.

You may assume that all words are unique and consist of lowercase letters.

outputFormat

Output a single line containing the k-th smallest word in lexicographical order.

4
banana apple cherry date
2

banana