Assembly Required

Princess Lucy broke her old reading lamp and needs a new one. The castle orders a shipment of parts from the Slick Lamp Parts Company, which produces interchangeable lamp pieces.

There are $m$ types of lamp pieces, and the shipment contains several pieces of each type. Making a lamp requires exactly one piece of each type. The princess likes each piece by some value, and she likes a lamp as much as the sum of how much she likes each of its pieces. Two different pieces are distinct even when their values are equal.

You are part of the castle staff, which has lately gotten fed up with the princess. The staff needs to propose $k$ distinct lamp combinations to the princess. Two combinations are distinct if they differ in at least one piece. The staff decides to propose the $k$ combinations she will like the least, that is, the $k$ combinations with the lowest values. How much will the princess like the $k$ combinations that the staff proposes?

The first line contains a single integer $T$ ($1 \le T \le 10$), the number of test cases.

The first line of each test case contains two integers: $m$ ($1 \le m \le 100$), the number of lamp piece types, and $k$ ($1 \le k \le 100$), the number of lamp combinations to propose.

Each of the next $m$ lines describes the pieces of one type. The line begins with $n_i$ ($2 \le n_i \le 100$), the number of pieces of this type, followed by $n_i$ integers $v_{i,1}, \ldots, v_{i,n_i}$ ($1 \le v_{i,j} \le 10000$) that give how much the princess likes each piece.

It is guaranteed that $k$ is no greater than the product of all $n_i$.

For each test case, print a single line with $k$ integers separated by spaces: how much the princess will like the proposed lamp combinations, in nondecreasing order.

In the first test case there are four lamp pieces, two of each type. The worst possible lamp has value $1 + 1 = 2$, and the second worst possible lamp has value $2 + 1 = 3$.