Challenge: The k Largest

Lab Python Beginner 10 points

Read a list of numbers and k. Using a min-heap of size k, print the k largest numbers from largest to smallest.

Input

Line 1: whole numbers. Line 2: k (1 ≤ k ≤ count).

Output

k numbers separated by spaces.

Example

Input

5 12 3 41 7 19 2 33
3

Output

41 33 19

Sample input available Sample output available

Editor

Python

Hints

Push each number; if the heap grows past k, pop the smallest.

At the end the heap holds the k largest.

Solution explanation

The heap never holds more than k items, so each step is O(log k).

Show solution

import heapq
nums = list(map(int, input().split()))
k = int(input())
heap = []
for x in nums:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)
print(" ".join(map(str, sorted(heap, reverse=True))))

Output

Answer