У Фермера Джона есть $$$n$$$ массивов $$$a_1, a_2, \ldots, a_n$$$, которые могут иметь разные длины. Он будет укладывать массивы друг на друга, в результате чего получится сетка с $$$n$$$ строками. Массивы выровнены по левому краю и могут быть уложены в любом порядке, в котором он пожелает.
Затем произойдет действие силы тяжести. Любая ячейка, которая не находится на нижнем ряду и не имеет элемента под собой, упадет на строку ниже. Этот процесс будет повторяться, пока не останется ячеек, которые удовлетворяют вышеуказанному условию.
Для всех возможных способов, которыми ФД может уложить массивы, выведите лексикографически минимальный нижний ряд после действия силы тяжести.
Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).
В следующих $$$n$$$ строках первое целое число $$$k_i$$$ ($$$1 \leq k \leq 2 \cdot 10^5$$$) обозначает длину $$$a_i$$$.
Затем следуют $$$k_i$$$ целых чисел, разделенных пробелами, $$$a_{i_1}, a_{i_2}, \ldots, a_{i_{k_i}}$$$ ($$$1 \leq a_{i_j} \leq 2 \cdot 10^5$$$).
Гарантируется, что сумма $$$n$$$ и сумма всех $$$k_i$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите лексикографически минимальный нижний ряд в новой строке.
413 5 2 722 2 93 3 1 431 52 5 12 5 233 4 4 97 7 6 5 4 3 2 14 2 4 5 1
5 2 7 2 9 4 5 1 2 4 5 1 3 2 1
Демонстрация для набора входных данных 2:
Демонстрация для набора входных данных 4:
| Codeforces Round 1050 (Div. 4) |
|---|
| Закончено |
