Турнір з армреслінгу#3328

Турнір з армреслінгу

3 секунди

64 мегабайти

Дуже легка

Як ви могли чути, пан Куміс проводить турнір з армрестлінгу. У цьому турнірі беруть участь $2^{N}$ 2^N учасників, пронумерованих від $1$ до $2^{N}$ 2^N. Перший учасник ( $C_{1}$ C_1) змагатиметься з другим учасником ( $C_{2}$ C_2). $C_{3}$ C_3 змагатиметься з $C_{4}$ C_4, і так далі. Переможець з пари $C_{1}$ C_1 і $C_{2}$ C_2 змагатиметься з переможцем пари $C_{3}$ C_3 і $C_{4}$ C_4. Переможець з пари $C_{5}$ C_5 і $C_{6}$ C_6 змагатиметься з переможцем пари $C_{7}$ C_7 і $C_{8}$ C_8, і так далі (див. діаграму нижче).

Кожен учасник спочатку має силу $P_{i}$ P_i. Коли два учасники змагаються, сильніший перемагає, і його сила зменшується на величину сили супротивника. Однак, перед наступним поєдинком він має час відновити свою силу і може відновити максимум $K$ одиниць сили, але його сила не може перевищити початкову ( $P_{i}$ P_i). Якщо два учасники мають однакову силу, перемагає той, у кого менший номер.

Враховуючи початкову силу всіх учасників, визначте, хто виграє турнір і яких учасників він переможе.

Вхідні дані

Перша строка вхідних даних містить ціле число $T$ ( $T \leq 100$ T \le 100), що позначає кількість тестів. Кожен тест починається з двох цілих чисел $N$ ( $1 \leq N \leq 15$ 1 \le N \le 15) і $K$ ( $0 \leq K \leq 1000$ 0 \le K \le 1000). Наступна строка містить $2^{N}$ 2^N цілих чисел $P_{i}$ P_i ( $1 \leq P_{i} \leq 1000$ 1 \le P_i \le 1000), що позначають початкову силу $i$ -го учасника для $i = 1, \dots, 2^{N}$ i = 1, \ldots, 2^N.

Вихідні дані

Для кожного тесту виведіть дві строки. Перша строка містить ціле число, що позначає переможця турніру. Друга строка містить $N$ цілих чисел, які є всіма учасниками, яких переможець переміг у порядку матчів. Кожне число відокремлене одним пробілом.

Приклади

Приклад 1