Challenge: Merge Sorted Lists

Lab Python Intermediate 20 points

Read m sorted lists and merge them into one sorted list using a heap (don't just join and sort).

Input

Line 1: m. Then m lines, each a sorted list of whole numbers.

Output

The merged list, separated by spaces.

Example

Input

Output

1 2 3 4 5 6 9 10

Sample input available Sample output available

Editor

Python

Hints

Start the heap with (first value, list number, position 0) for every list.

After popping, push the next value from the same list.

Solution explanation

The heap only holds one item per list, so merging N total items from m lists is O(N log m).

Show solution

import heapq
m = int(input())
lists = [list(map(int, input().split())) for _ in range(m)]
heap = [(l[0], i, 0) for i, l in enumerate(lists) if l]
heapq.heapify(heap)
out = []
while heap:
    v, i, j = heapq.heappop(heap)
    out.append(v)
    if j + 1 < len(lists[i]):
        heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
print(" ".join(map(str, out)))

Output

Answer