学习绘画

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一排 $n$ 个格子，可以任意选择其中一些格子涂色。一次方案中，设所有极大的连续涂色段为 $[l_1,r_1],\ldots,[l_x,r_x]$，其美丽值为 $\sum a_{l_i,r_i}$。

在全部 $2^n$ 种涂色方案中，求最大的 $k$ 个美丽值。结果可重复，并保证至少存在 $k$ 种方案。

输入格式

第一行一个整数 $t$。每组先输入 $n,k$。接下来第 $i$ 行输入 $n-i+1$ 个整数 $a_{i,i},a_{i,i+1},\ldots,a_{i,n}$。

输出格式

每组按非递增顺序输出 $k$ 个整数。

样例输入

2
1 2
-5
2 4
2 -3
-1

样例输出

0 -5
2 0 -1 -3

数据范围

对于所有数据，$1\le t\le10^3$，$1\le n\le10^3$，$1\le k\le\min(2^n,5000)$，$|a_{i,j}|\le10^6$；所有测试用例的 $n$ 之和不超过 $10^3$，$k$ 之和不超过 $5000$。