Merge K Sorted Lists

You are given $k$ sorted lists. Your task is to merge these lists into a single sorted list.

The input starts with an integer $k$ which represents the number of sorted lists. Each of the following $k$ lines begins with an integer $n_i$ indicating the number of elements in that list, followed by $n_i$ integers in non-decreasing order.

Your output should be a single line (printed to stdout) containing the merged sorted list with the numbers separated by a single space.

Hint: An efficient approach is to use a min-heap (priority queue) to achieve a time complexity of $O(N \log k)$, where $N$ is the total number of elements, which ensures that the solution scales well.

inputFormat

The input is provided via stdin with the following format:

1. The first line contains an integer $k$, the number of sorted lists.
2. Each of the next $k$ lines represents a sorted list. The line starts with an integer $n_i$ (the number of elements in the list) followed by $n_i$ space-separated integers.

outputFormat

The output, printed to stdout, is a single line containing the merged sorted list. The numbers should be separated by a single space.

3
3 1 3 5
4 2 4 6 8
2 0 7

0 1 2 3 4 5 6 7 8