Top K Frequent Words

Given a list of words and an integer k, your task is to output the k most frequent words from the list. The words should be ordered primarily by their frequency in descending order and secondarily by the order of their first appearance in the list.

Formally, let \(f(w)\) denote the frequency of word \(w\) and \(i(w)\) denote its first index of occurrence (0-indexed). Then for any two distinct words \(w_1\) and \(w_2\), \(w_1\) appears before \(w_2\) if and only if:

$$ f(w_1) > f(w_2) \quad \text{or} \quad (f(w_1) = f(w_2) \quad \text{and} \quad i(w_1) < i(w_2)) $$

If k is larger than the number of unique words, output all unique words following the above ordering.

inputFormat

Input is read from standard input (stdin). The first line contains an integer n representing the number of words. The second line contains n words separated by spaces. The third line contains an integer k.

outputFormat

Output the k most frequent words in one line to standard output (stdout), separated by a single space.## sample

6
apple banana apple orange banana apple
2

apple banana