Nth Most Frequent Word

You are given a list of words and an integer n. Your task is to find the n^th most frequently occurring word in the list. The ranking is determined by the frequency of occurrence in non‐increasing order. In case of ties (i.e. multiple words having the same frequency), the word that is lexicographically smallest ranks higher.

Formally, suppose that each distinct word w appears f(w) times. Let the words be sorted in descending order by their frequency and, if two words share the same frequency, in ascending lexicographical order. You are to output the word that is at the n^th position in this sorted order.

If the value of n is greater than the number of distinct words, output None (without quotes).

The sorting criteria can be written in LaTeX as follows:

$$ \text{Sort by } (-f(w), w) $$

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer k representing the number of words in the list.
• The second line contains k space-separated words.
• The third line contains an integer n, representing the ranking position to retrieve.

outputFormat

Output the n^th most frequent word to standard output (stdout). If no such word exists, output None.

## sample

6
apple banana apple orange banana apple
1

apple

</p>