Elsie 正在学习绘画。她的画布上有 $$$n$$$ 个单元格,编号从 $$$1$$$ 到 $$$n$$$,并且可以绘制任何(可能是空的)单元格子集。
Elsie 有一个二维数组 $$$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$$$ 种方法来绘制条带。在所有这些方法中,帮助 Elsie 找到她可以获得的一幅画的最大可能价值 $$$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$$$ 个整数必须代表 Elsie 可以获得的第 $$$i$$$ 个最大的绘画美感值。
示例
输入 #1
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
输出 #1
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
注意
在第一个测试用例中,Elsie 可以绘制唯一的单元格,也可以不绘制它。如果她画唯一的细胞,这幅画的美丽程度为$$$-5$$$。如果她选择不画它,这幅画的美丽就是$$$0$$$。因此,她可以获得的最大美丽是$$$0$$$,她可以获得的第二大美丽是$$$-5$$$。
下面是第三个测试用例的图示。