D. Учимся рисовать
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Элси учится рисовать. У нее есть холст из $$$n$$$ клеток, пронумерованных от $$$1$$$ до $$$n$$$, и она может раскрасить любое (возможно, пустое) подмножество клеток.

У Элси есть двумерный массив $$$a$$$, который она будет использовать для оценки картин. Пусть максимальные непрерывные отрезки закрашенных клеток в картине равны $$$[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$$$. Красота картины — это сумма $$$a_{l_i,r_i}$$$ по всем $$$1 \le i \le x$$$. На изображении выше максимальные непрерывные отрезки закрашенных клеток равны $$$[2,4],[6,6],[8,9]$$$, а красота картины равна $$$a_{2,4}+a_{6,6}+a_{8,9}$$$.

Всего есть $$$2^n$$$ различных способов раскрасить холст. Помогите Элси найти $$$k$$$ наибольших значений красоты картины, которые она может получить, среди всех способов. Обратите внимание, что эти $$$k$$$ значений не обязательно должны быть различными. Гарантируется, что существует не менее $$$k$$$ различных способов раскрасить холст.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит $$$2$$$ целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^3$$$, $$$1 \leq k \leq \min(2^n, 5 \cdot 10^3)$$$) — количество клеток и количество наибольших значений красоты картины, которые вы должны найти.

Следующие $$$n$$$ строк каждого набора входных данных описывают двумерный массив $$$a$$$, $$$i$$$-я строка содержит $$$n-i+1$$$ целых чисел $$$a_{i,i},a_{i,i+1},\ldots,a_{i,n}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$, а сумма $$$k$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^3$$$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке $$$k$$$ целых чисел: $$$i$$$-е из них должно равняться $$$i$$$-му наибольшему значение красоты картины, которое может получить Элси.

Пример
Входные данные
4
1 2
-5
2 4
2 -3
-1
3 8
2 4 3
1 3
5
6 20
0 -6 -3 0 -6 -2
-7 -5 -2 -3 -4
7 0 -9 -4
2 -1 1
1 -2
-6
Выходные данные
0 -5 
2 0 -1 -3 
7 5 4 3 3 2 1 0 
8 8 7 7 5 5 2 2 1 1 1 1 1 1 0 0 0 0 0 -1 
Примечание

В первом наборе входных данных Элси может либо закрасить единственную клетку, либо не закрашивать ее. Если она раскрасит единственную клетку, красота картины составит $$$-5$$$. Если она решит не раскрашивать ее, красота картины составит $$$0$$$. Таким образом, наибольшая красота, которую она может получить, равна $$$0$$$, а вторая по величине красота, которую она может получить, равна $$$-5$$$.

Ниже приведена иллюстрация третьего набора входных данных.