H. Щелчок Таноса
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Piotr Rubik - Psalm dla Ciebie
ඞ

Имеется массив $$$a$$$ длины $$$2^k$$$, который изначально является перестановкой значений от $$$1$$$ до $$$2^k$$$ для некоторого целого положительного числа $$$k$$$. Алиса и Боб играют в следующую игру на массиве $$$a$$$. Сначала Алисе и Бобу даётся значение $$$t$$$ между $$$1$$$ и $$$k$$$. Затем, ровно $$$t$$$ ходов происходит следующее:

  • Алиса либо ничего не делает, либо выбирает два различных элемента массива $$$a$$$ и меняет их местами.
  • Боб выбирает либо левую половину, либо правую половину массива $$$a$$$, и стирает её.

Счет игры определяется как максимальное значение в $$$a$$$ после всех $$$t$$$ ходов. Алиса хочет максимизировать этот счет, а Боб — минимизировать.

Вам нужно вывести $$$k$$$ чисел: счет игры, если и Алиса, и Боб играют оптимально, для всех $$$t$$$ от $$$1$$$ до $$$k$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$k$$$ ($$$1 \le k \le 20$$$) — параметр длины массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$2^k$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$1 \le a_i \le 2^k$$$, $$$a_i$$$ попарно различны) — заданный массив $$$a$$$.

Гарантируется, что сумма $$$2^k$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.

Выходные данные

Для каждого набора входных данных выведите $$$k$$$ чисел, где $$$i$$$-е число — это счет игры, если Алиса и Боб играют оптимально, а игра длится $$$t = i$$$ ходов.

Пример
Входные данные
5
1
1 2
2
4 3 2 1
3
5 1 6 4 7 2 8 3
4
10 15 6 12 1 3 4 9 13 5 7 16 14 11 2 8
5
32 2 5 23 19 17 31 7 29 3 4 16 13 9 30 24 14 1 8 20 6 15 26 18 10 27 22 12 25 21 28 11
Выходные данные
1
3 1
7 5 1
15 13 9 1
31 28 25 17 1
Примечание

В третьем наборе входных данных, для $$$t = 2$$$, игра могла бы проходить следующим образом:

  • Изначально, $$$a = [5, 1, 6, 4, 7, 2, 8, 3]$$$.
  • Алиса меняет местами $$$a_6$$$ и $$$a_8$$$, $$$a$$$ становится $$$[5, 1, 6, 4, 7, 3, 8, 2]$$$.
  • Боб стирает правую половину массива, $$$a$$$ становится $$$[5, 1, 6, 4]$$$.
  • Алиса ничего не делает, $$$a$$$ остается $$$[5, 1, 6, 4]$$$.
  • Боб стирает правую половину массива, $$$a$$$ становится $$$[5, 1]$$$.
  • Игра заканчивается со счётом $$$5$$$.