Drazil 非常喜欢堆。所以他创造了一个堆问题:
在数组上实现了一个高度为 $$$h$$$ 的最大堆。该堆的详细信息如下:
该堆恰好包含 $$$2^h - 1$$$ 个不同的正非零整数。所有整数都是不同的。这些数字存储在数组 $$$a$$$ 中,索引从 $$$1$$$ 到 $$$2^h-1$$$。对于任意 $$$1 < i < 2^h$$$,$$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$。
现在我们要减小该堆的高度,使高度变为 $$$g$$$,堆中的数字恰好为 $$$2^g-1$$$。要降低高度,我们应该执行以下操作 $$$2^h-2^g$$$ 次:
选择一个索引$$$i$$$,其中包含一个元素,并在索引$$$i$$$中调用以下函数$$$f$$$:
请注意,我们假设如果 $$$a[i]=0$$$,则索引 $$$i$$$ 不包含元素。
在所有操作之后,剩余的 $$$2^g-1$$$ 元素必须位于从 $$$1$$$ 到 $$$2^g-1$$$ 的索引中。现在 Drazil 想知道剩余 $$$2^g-1$$$ 元素的最小可能总和是多少。请找到这个总和并找到实现该值的函数调用序列。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 70\,000$$$):测试用例的数量。
每个测试用例包含两行。第一行包含两个整数 $$$h$$$ 和 $$$g$$$ ($$$1 \leq g < h \leq 20$$$)。第二行包含 $$$n = 2^h-1$$$ 不同的正整数 $$$a[1], a[2], \ldots, a[n]$$$ ($$$1 \leq a[i] < 2^{20}$$$)。对于从 $$$2$$$ 到 $$$2^h - 1$$$ 的所有 $$$i$$$,$$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$。
$$$n$$$ 的总和小于 $$$2^{20}$$$。
输出
对于每个测试用例,打印两行。
第一行应包含一个整数,表示将堆高度减少到 $$$g$$$ 后的最小总和。第二行应包含 $$$2^h - 2^g$$$ 整数 $$$v_1, v_2, \ldots, v_{2^h-2^g}$$$。在第 $$$i$$$ 操作中,应调用 $$$f(v_i)$$$。
示例
输入 #1
2 3 2 7 6 3 5 4 2 1 3 2 7 6 5 4 3 2 1
输出 #1
10 3 2 3 1 8 2 1 3 1