Word Frequency Query

You are given a series of queries where each query is either an ADD command or a QUERY command. The ADD command adds a word to a frequency counter (converting it to lowercase) and the QUERY command asks for the top k most frequent words so far. The words should be sorted primarily by their frequency in descending order, and in case of ties, by lexicographical order in ascending order. For each QUERY command, print the resulting words each on a new line followed by an empty line to separate the results for different queries.

Note: The words are treated in a case-insensitive manner.

The ranking rule can be formally expressed as follows. Let \(f(w)\) be the frequency of word \(w\). When comparing two distinct words \(w_1\) and \(w_2\):

[ \text{if } f(w_1) \neq f(w_2):\quad w_1 \text{ comes before } w_2 \iff f(w_1) > f(w_2), ]

[ \text{if } f(w_1) = f(w_2):\quad w_1 \text{ comes before } w_2 \iff w_1 < w_2 \text{ (lexicographically)}. ]

inputFormat

The first line of input contains an integer Q which denotes the number of queries. The following Q lines each contain a query command in one of the following formats:

• ADD word: Add the word to the frequency counter. The word contains only alphabets.
• QUERY k: Output the top k most frequent words based on the criteria described above.

outputFormat

For each QUERY command, output the resulting words each on a new line in order. After each query's output, print an empty line (i.e. a blank line) to separate it from the next query's output.

## sample

4
ADD apple
QUERY 1
ADD banana
QUERY 2

apple
apple
banana

</p>