EduBrick

G. Хвост слияния

2000 мс · 256 МБ · всё или ничего

Даны kk неубывающих последовательностей. Выведите последние mm элементов их слияния — то есть mm наибольших чисел среди всех, с учётом кратности, в порядке неубывания.

Формат ввода

Первая строка содержит числа kk и mm (1≤k≤1051 \le k \le 10^5).

Следующие kk строк описывают последовательности: сначала длина lenilen_i, затем lenilen_i чисел в порядке неубывания. Сумма длин не превосходит 2⋅1052 \cdot 10^5, и 1≤m≤1 \le m \le сумме длин.

Все числа целые и по модулю не превосходят 10910^9.

Формат вывода

Выведите mm чисел — хвост слияния в порядке неубывания.

Примеры

ввод
3 5
2 1 4
3 2 3 9
1 0
вывод
1 2 3 4 9
Войдите, чтобы отправлять решения.