Merge K Sorted Arrays Problem Statement

Given 'K' different arrays that are individually sorted in ascending order, merge all these arrays into a single array that is also sorted in ascending order.

Input

The first line of input contains an integer T, the number of test cases. The first line of each test case contains an integer that denotes the value of K. The next 2*K lines of each test case follow: The first line contains an integer ‘N’ denoting the size of the array. The second line contains N space-separated integers.

Output

The first and only line of output contains space-separated elements of the merged and sorted array, as described in the task.

Example

Input:

1 2 3 1 3 5 2 2 6

Output:

1 2 3 5 6

Constraints

1 ≤ T ≤ 5

1 ≤ K ≤ 5

1 ≤ N ≤ 20

-10^5 ≤ DATA ≤ 10^5

Time Limit: 1 sec

Note

You don’t have to print anything; it has already been taken care of. Just implement the function.

Question

Merge K Sorted Arrays Problem Statement

Given 'K' different arrays that are individually sorted in ascending order, merge all these arrays into a single array that is also sorted in ascending order.

Input

The first line of input contains an integer T, the number of test cases.

The first line of each test case contains an integer that denotes the value of K.

The next 2*K lines of each test case follow: 
The first line contains an integer ‘N’ denoting the size of the array. 

The second line contains N space-separated integers.

Output

The first and only line of output contains space-separated elements of the merged and sorted array, as described in the task.

Example

Input:

Output:

1 2 3 5 6

Constraints

1 ≤ T ≤ 5
1 ≤ K ≤ 5
1 ≤ N ≤ 20
-10^5 ≤ DATA ≤ 10^5
Time Limit: 1 sec

Note

You don’t have to print anything; it has already been taken care of. Just implement the function.

Accepted Answer

Merge K sorted arrays into a single sorted array.

Create a min heap to store the first element of each array along with the array index.
Pop the top element from the heap, add it to the result array, and push the next element from the same array back to the heap.
Repeat the process until all elements are processed.
Time complexity: O(N log K) where N is the total number of elements and K is the number of arrays.