Merge k Sorted Arrays

You are given k sorted arrays. Your mission is to merge these sorted arrays into a single sorted array. This task requires you to efficiently merge multiple sorted lists and output the merged sorted sequence.

The input begins with an integer k representing the number of arrays. For each array, the first number denotes its length, followed by the sorted elements of that array. You need to output a single line containing the merged sorted array with each element separated by a space.

Mathematically, if the arrays are \(A_1, A_2, \ldots, A_k\), you must produce an array \(B\) such that \(B\) is a sorted combination of all elements from \(A_1, A_2, \ldots, A_k\).

inputFormat

The input is given from STDIN and has the following format:

1. An integer k indicating the number of arrays.
2. For each of the k arrays, a line starting with an integer n_i (the length of the i-th array), followed by n_i space-separated integers in sorted order.

Example:

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

outputFormat

Output a single line to STDOUT containing the merged sorted array with each element separated by a space.

For the sample input above, the output should be:

1 2 3 4 5 6 7 8 9

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

1 2 3 4 5 6 7 8 9