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 < i < 2^h $ , $ a[i] < 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.

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 < 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] < 2^{20} $ ). For all $ i $ from $ 2 $ to $ 2^h - 1 $ , $ a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor] $ . The total sum of $ n $ is less than $ 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.