Background

The original time limit was 5 s. The time limit here has been adjusted according to the speed of Luogu's judge machines.

Problem Description

Translated from COCI 2009.11 T6 “PASIJANS”

You are given $N$ stacks that already contain numbers (the number of elements in each stack may be different), and an empty “answer queue”. Each time, you may “pop the top element of one stack and append it to the end of the answer queue”, until all stacks become empty. Find the lexicographically smallest possible answer queue.

If two answer queues $a, b$ (from front to back) have the same first $i-1$ numbers, and $a_i<b_i$, then we say the lexicographical order of $a$ is smaller than that of $b$.

Input Format

The first line contains an integer $N$.
In the next $N$ lines, the first integer is $L$, the number of elements in the stack. Then $L$ integers are given in order from the top of the stack to the bottom.

Output Format

Output $\sum L$ integers, representing the lexicographically smallest answer queue.

3
1 2
1 100
1 1

1 2 100

2
5 10 20 30 40 50
2 28 27

10 20 28 27 30 40 50

2
3 5 1 2
3 5 1 1

5 1 1 5 1 2

Hint

$1\le N\le 1000,$ $1\le L\le 1000$。

Translated by ChatGPT 5