You are given an array of 𝑘 linked lists, where each linked list is sorted in ascending order.

Your task is to merge all the linked lists into one sorted linked list and return the merged list.

The algorithm must run in O(N log 𝑘) time complexity, and it should use a heap-based approach.

Input Format

The first line contains an integer 𝑘, the number of linked lists.

Each of the next 𝑘 lines contains a sequence of integers representing a linked list.

The first integer in each line is 𝑚, the number of nodes in the list.

This is followed by 𝑚 integers representing the node values in ascending order. Output Format

Print the merged linked list as space-separated integers in ascending order.

If the merged list is empty, print an empty line.

Example 1

Input:

3
3 1 4 5
3 1 3 4
2 2 6

Output:

1 1 2 3 4 4 5 6

Example 2

Input:

2
4 2 4 6 8
3 1 3 5

Output:

1 2 3 4 5 6 8

Constraints

0 ≤ k ≤ 10⁴

0 ≤ m ≤ 500 (length of each linked list)

-10⁴ ≤ list[i][j] ≤ 10⁴

The sum of all linked list lengths will not exceed 10⁴