Top Dishes

You are given a list of customer orders, where each order consists of the name of a dish and a timestamp. Your task is to determine the top N most frequently ordered dishes. In case of a tie (i.e. two or more dishes have the same frequency), the dish with the lexicographically smaller name should come first.

The input is given via standard input and the output should be printed to standard output. The answer must list the dish names separated by a single space on one line. If there are no orders, output an empty line.

Note: All dish names are case-sensitive.

LaTeX Formula: Sorting rule can be written as: sort by \( (-frequency, name) \).

inputFormat

The first line contains a single integer \( M \) representing the number of orders.

The next \( M \) lines each contain a dish name (a string without spaces) and a timestamp (an integer), separated by a space.

The following line contains an integer \( N \) representing the number of top dishes to output.

outputFormat

Output a single line containing the top \( N \) dish names separated by spaces. If there are no orders or if \( N = 0 \), output an empty line.

6
Burger 1617420000
Pizza 1617420100
Burger 1617420200
Burger 1617420300
Pizza 1617420400
Salad 1617420500
2

Burger Pizza