CF1942D.Learning to Paint

Elsie 正在学习绘画。她有一个由 $n$ 个格子组成的画布，格子编号从 $1$ 到 $n$，她可以选择涂色任意（可能为空）的格子子集。

Elsie 有一个二维数组 $a$，她将用它来评价画作。对于某个画作，设其被涂色的最大连续区间为 $[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$。该画作的美丽值为所有 $a_{l_i,r_i}$ 之和，即 $\sum_{i=1}^x a_{l_i,r_i}$。在上图中，被涂色的最大连续区间为 $[2,4],[6,6],[8,9]$，该画作的美丽值为 $a_{2,4}+a_{6,6}+a_{8,9}$。

总共有 $2^n$ 种涂色方式。请你帮助 Elsie 找出所有这些方式中最大的 $k$ 个美丽值。注意，这 $k$ 个值不一定互不相同。保证至少存在 $k$ 种不同的涂色方式。

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例数量。

每个测试用例的第一行包含两个整数 $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$ 个整数，表示 Elsie 能获得的第 $i$ 大美丽值。

在第一个测试用例中，Elsie 可以选择涂色或不涂色唯一的格子。如果她涂色，画作的美丽值为 $-5$；如果不涂色，美丽值为 $0$。因此，她能获得的最大美丽值为 $0$，第二大美丽值为 $-5$。

下图展示了第三个测试用例的示意。

由 ChatGPT 4.1 翻译