题目描述

chitanda 有 $k$ 个卡包，第 $i$ 个卡包里有 $ci$ 张卡，每张卡有一个能力值，其中第 $i$ 个卡包里的第 $j$ 张卡具有 $a{i, j}$ 点能力值。

他准备选择 $k$ 张卡牌的组合，其中每个卡包要选择恰好一张卡牌。他希望这 $k$ 张卡牌的能力值之和尽量大，请你告诉他在所有可能的组合里，能力值之和最大的 $n$ 个组合分别具有多大的能力值。

输入格式

第一行包含两个整数 $k$ 和 $n$，含义见题目描述。

接下来 $k$ 行，每行描述一个卡包的信息，其中第 $i$ 行的第一个整数表示 $c_i$，接下来该行会有 $c_i$ 个整数，依次表示这个卡包里每张卡的能力值。

输出格式

输出一行，包含 $n$ 个整数，相邻两个数字之间用空格隔开，其中第 $i$ 个整数表示第 $i$ 大的能力值之和。

样例

input

2 9
3 1 3 5
3 2 3 3

output

8 8 7 6 6 5 4 4 3

chitanda 有 $3 \times 3$ 种选法，能力值分别为 $1 + 2, 1 + 3, 1 + 3, 3 + 2, 3 + 3, 3 + 3, 5 + 2, 5 + 3, 5 + 3$。

数据范围与提示

对于所有数据，$k \geq 2,$ $1 \leq n \leq \prod\limits_{i = 1}^{k}{c_i},$ $ci \geq 1,$ $1 \leq a{i, j} \leq 10^9$ $(i = 1, 2, \cdots, k; j = 1, 2, \cdots, c_i)$。