Top N Frequent Strings

You are given a list of strings and an integer n. Your task is to determine the n most frequent strings from the list.

The strings should be ordered primarily by their frequency in descending order, and in case of a tie, they should be sorted lexicographically in ascending order. Formally, if we denote the frequency of a string s by \( f(s) \), then for two strings \( s_1 \) and \( s_2 \), \( s_1 \) should appear before \( s_2 \) if \( f(s_1) > f(s_2) \) or \( f(s_1) = f(s_2) \) and \( s_1 < s_2 \) (lexicographically).

Input format: The input is read from standard input. The first line contains an integer \( m \) denoting the number of strings. The next \( m \) lines each contain a single string. The final line contains the integer \( n \), indicating the number of most frequent strings to output.

Output format: Print the top n strings in one line separated by a single space.

Example:

Input:
6
apple
banana
apple
orange
banana
apple
2
Output:
apple banana

</p>

inputFormat

The first line of input contains an integer \( m \) (the number of strings). Followed by \( m \) lines each containing a non-empty string. The last line contains an integer \( n \) (the number of top frequent strings to return).

outputFormat

Output a single line with the n most frequent strings, separated by a single space, arranged in descending order by frequency, with lexicographical order used for ties.

## sample

6
apple
banana
apple
orange
banana
apple
2

apple banana