← 返回题目列表

Codeforces · 2148/F

F. 重力坠落

中文机器翻译题面 查看原题

Farmer John 有 $$$n$$$ 数组 $$$a_1, a_2, \ldots, a_n$$$ 可能有不同的长度。他会将数组堆叠在一起,形成一个包含 $$$n$$$ 行的网格。数组是左对齐的,并且可以按照他想要的任何顺序堆叠。

然后,重力就会发生。任何不在底行且其下方没有元素的单元格都会落下一行。将重复该过程,直到没有满足上述约束的小区为止。

在 FJ 堆叠数组的所有可能方式中,输出重力发生后按字典顺序排列的最小底行。

输入

第一行包含 $$$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$$$。

输出

对于每个测试用例,在新行上输出字典顺序最小的底行。

示例

输入
复制

4
1
3 5 2 7
2
2 2 9
3 3 1 4
3
1 5
2 5 1
2 5 2
3
3 4 4 9
7 7 6 5 4 3 2 1
4 2 4 5 1

输出
复制

5 2 7 
2 9 4 
5 1 
2 4 5 1 3 2 1 

注意

测试用例2演示:

测试用例4演示: