A college radio station logged n song requests as song IDs. Print the k most requested songs, most requested first. If two songs have the same number of requests, the one with the larger ID comes first.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ k ≤ number of distinct IDs
- 1 ≤ ID ≤ 10^9
Input and output
- Input
- Line 1: n and k. Line 2: n song IDs.
- Output
- k song IDs on one line.
Examples
Input 1
8 2
4 4 4 7 7 9 9 1Output
4 94 appears 3 times. 7 and 9 both appear twice; the tie goes to the larger value, 9.
Input 2
3 2
5 6 5Output
5 65 appears twice and 6 once, so the order is 5 then 6.
Show hints
- Count first with a hash map.
- Keep a min-heap of size k keyed by (count, ID); the smallest entry is the one to drop.
Show the explanation
Count each ID in a hash map. Then keep a min-heap of size k ordered by (count, id): push each distinct ID, and pop the smallest whenever the heap exceeds k. What remains are the k best; pop them all and reverse to print best first. This is O(n + d log k) for d distinct IDs, better than sorting everything when k is small. (Bucket sort by count gives O(n).)
Original UniCircle question. Last reviewed 22 Oct 2026.