CF1329C.Drazil Likes Heap

Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height $h$ implemented on the array. The details of this heap are the following:

This heap contains exactly $2^h - 1$ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $a$ indexed from $1$ to $2^h-1$. For any $1 \lt i \lt 2^h$, $a[i] \lt a[\left \lfloor{\frac{i}{2}}\right \rfloor]$.

Now we want to reduce the height of this heap such that the height becomes $g$ with exactly $2^g-1$ numbers in heap. To reduce the height, we should perform the following action $2^h-2^g$ times:

Choose an index $i$, which contains an element and call the following function $f$ in index $i$:

Note that we suppose that if $a[i]=0$, then index $i$ don't contain an element.

After all operations, the remaining $2^g-1$ element must be located in indices from $1$ to $2^g-1$. Now Drazil wonders what's the minimum possible sum of the remaining $2^g-1$ elements. Please find this sum and find a sequence of the function calls to achieve this value.

Drazil 非常喜欢堆，因此他设计了一个关于堆的问题：

有一个高度为 $h$ 的最大堆，用数组实现。该堆的具体细节如下：

• 该堆恰好包含 $2^h - 1$ 个互不相同的正整数（非零）；
• 所有整数互不相同；
• 这些数存储在数组 $a$ 中，下标从 $1$ 到 $2^h-1$；
• 对任意 $1 \lt i \lt 2^h$，均有 $a[i] \lt a[\left \lfloor{\frac{i}{2}}\right \rfloor]$。

现在我们希望将该堆的高度缩减至 $g$，使得堆中恰好剩下 $2^g-1$ 个元素。为缩减高度，需执行以下操作共 $2^h-2^g$ 次：

• 选择一个当前存有元素的下标 $i$，并在该下标上调用如下函数 $f$：

注意：我们约定，若 $a[i]=0$，则认为下标 $i$ 处不包含元素。

所有操作完成后，剩余的 $2^g-1$ 个元素必须位于下标 $1$ 至 $2^g-1$ 的位置上。现在 Drazil 想知道：剩余 $2^g-1$ 个元素的和的最小可能值是多少？请找出该最小和，并给出一组实现该最小和的函数调用序列。

The first line of the input contains an integer $t$ ($1 \leq t \leq 70\,000$): the number of test cases.

Each test case contain two lines. The first line contains two integers $h$ and $g$ ($1 \leq g \lt h \leq 20$). The second line contains $n = 2^h-1$ distinct positive integers $a[1], a[2], \ldots, a[n]$ ($1 \leq a[i] \lt 2^{20}$). For all $i$ from $2$ to $2^h - 1$, $a[i] \lt a[\left \lfloor{\frac{i}{2}}\right \rfloor]$.

The total sum of $n$ is less than $2^{20}$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 70\,000$）：测试用例的数量。

每个测试用例包含两行。第一行包含两个整数 $h$ 和 $g$（$1 \leq g \lt h \leq 20$）。第二行包含 $n = 2^h-1$ 个互不相同的正整数 $a[1], a[2], \ldots, a[n]$（$1 \leq a[i] \lt 2^{20}$）。对于所有从 $2$ 到 $2^h - 1$ 的 $i$，均满足 $a[i] \lt a[\left \lfloor{\frac{i}{2}}\right \rfloor]$。

所有测试用例中 $n$ 的总和小于 $2^{20}$。

For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to $g$. The second line should contain $2^h - 2^g$ integers $v_1, v_2, \ldots, v_{2^h-2^g}$. In $i$-th operation $f(v_i)$ should be called.

对于每个测试用例，输出两行。

第一行应包含一个整数，表示将堆的高度减少至 $g$ 后的最小总和。
第二行应包含 $2^h - 2^g$ 个整数 $v_1, v_2, \ldots, v_{2^h-2^g}$；在第 $i$ 次操作中应调用 $f(v_i)$。