Lexicographically Smallest Solitaire

This problem is adapted from COCI 2009.11 T6 "PASIJANS".

You are given \(N\) stacks, each pre‐filled with several numbers. The numbers in each stack are given in the order from bottom to top. In addition, you have an initially empty answer queue. You may perform the following operation any number of times until all stacks are empty:

[ \text{Choose any non‐empty stack, pop its top element, and append it to the end of the answer queue.} ]

Your task is to determine the lexicographically smallest answer queue that can be obtained. Formally, if two answer queues \(a\) and \(b\) (listed from front to rear) satisfy \(a_1 = b_1, \; a_2 = b_2, \; \dots, \; a_{i-1} = b_{i-1}\) and \(a_i < b_i\), then queue \(a\) is lexicographically smaller than queue \(b\).

inputFormat

The first line contains an integer \(N\) (the number of stacks). Each of the next \(N\) lines begins with an integer \(m\) (the number of elements in that stack), followed by \(m\) integers representing the numbers in that stack in order from bottom to top.

outputFormat

Output a single line with the lexicographically smallest answer queue. The numbers should be separated by a single space.

sample

2
3 1 2 3
3 1 3 2

2 3 1 3 2 1