Gravity Falls ( Try not using GPT )

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Python
Điểm: 20 Thời gian: 3.0s Bộ nhớ: 3M Input: bàn phím Output: màn hình

Farmer John has n arrays a1,a2,…,an 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.

Data

  • The first line contains t (1 ≤ t ≤ 1000) — the number of test cases.
  • The first line of each test case contains n (1 ≤ n ≤ 2*10^5).
  • For the following n lines, the first integer ki ( 1 ≤ k ≤ 2*10^5)denotes the length of Ai
  • Then, ki space-separated integers ai1,ai2,…,ai ki follow (1 ≤ aij ≤ 2*10^5).
  • It is guaranteed that the sum of n and the sum of all ki over all test cases does not exceed 2*10^5.

Result:

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

*Example:

Input1

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

Output

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

Note

Demonstration for test case 2:

Demonstration for test case 4:


Bình luận

Không có bình luận nào.