CF2148F Gravity Falls

Farmer John has $ n $ arrays $ a_1, a_2, \ldots, a_n $ that may have different lengths. He will stack the arrays on top of each other, resulting in a grid with $ n $ rows. The arrays are left-aligned and can be stacked in any order he desires. Then, gravity will take place. Any cell that is not on the bottom row and does not have an element beneath it will fall down a row. This process will be repeated until there are no cells that satisfy the aforementioned constraint. Over all possible ways FJ can stack the arrays, output the lexicographically minimum bottom row after gravity takes place.

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ). For the following $ n $ lines, the first integer $ k_i $ ( $ 1 \leq k \leq 2 \cdot 10^5 $ ) denotes the length of $ a_i $ . Then, $ k_i $ space-separated integers $ a_{i_1}, a_{i_2}, \ldots, a_{i_{k_i}} $ follow ( $ 1 \leq a_{i_j} \leq 2 \cdot 10^5 $ ). It is guaranteed that the sum of $ n $ and the sum of all $ k_i $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the lexicographically minimum bottom row on a new line.

Demonstration for test case 2: Demonstration for test case 4: