K Smallest Block Pile Weights

Y has n boxes of building blocks. Each box contains several blocks, and each block has a weight. Y wants to pick exactly one block from each box to form a pile, whose total weight is the sum of the weights of the selected blocks. Your task is to determine the smallest k total weights possible among all possible selections. Note that if two different selection methods yield the same total weight, that weight should be output as many times as it occurs.

The weight sum for a selection is defined as:

\( S = \sum_{i=1}^{n} w_{i} \)

where \( w_{i} \) is the weight of the chosen block from box \( i \).

inputFormat

The first line contains two integers n and k (1 ≤ n, k ≤ 10⁵ in the worst case, though inputs will be small enough for merging approach) — the number of boxes and the number of smallest sums to output.

Then follow n lines. The i-th line begins with an integer mi indicating the number of blocks in the i-th box, followed by mi integers representing the weight of each block. Each weight is a positive integer.

It is guaranteed that there is at least one block in each box.

outputFormat

Output exactly k lines, each containing one integer — the total weight of one of the k smallest selection methods in non-decreasing order. If there are multiple selections with the same total weight, they should be output as many times as they occur.

sample

2 3
2 1 2
2 3 4

4
5
5