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\), который содержит элемент, и запустить функцию \(f\) от индекса \(i\):
Обратите внимание, что мы считаем, что если \(a[i]=0\), то индекс \(i\) не содержит элемент.
После всех операций, оставшиеся \(2^g-1\) элементов должны находиться в индексах от \(1\) до \(2^g-1\). Теперь Drazil хочет узнать, какая может быть минимальная сумма оставшихся \(2^g-1\) элементов. Пожалуйста, найдите эту сумму и последовательность вызовов функции, на которой эта сумма достигается.
Выходные данные
Для каждого набора входных данных, выведите две строки.
В первой строке вы должны вывести минимальную сумму элементов после уменьшения глубины кучи до \(g\). Вторая строка должна содержать \(2^h - 2^g\) целых чисел \(v_1, v_2, \ldots, v_{2^h-2^g}\). В \(i\)-й операции должна быть вызвана \(f(v_i)\).