Piotr Rubik - Psalm dla Ciebie

ඞ

There is an array $$$a$$$ of size $$$2^k$$$ for some positive integer $$$k$$$, which is initially a permutation of values from $$$1$$$ to $$$2^k$$$. Alice and Bob play the following game on the array $$$a$$$. First, a value $$$t$$$ between $$$1$$$ and $$$k$$$ is shown to both Alice and Bob. Then, for exactly $$$t$$$ turns, the following happens:

Alice either does nothing, or chooses two distinct elements of the array $$$a$$$ and swaps them.
Bob chooses either the left half or the right half of the array $$$a$$$ and erases it.

The score of the game is defined as the maximum value in $$$a$$$ after all $$$t$$$ turns have been played. Alice wants to maximize this score, while Bob wants to minimize it.

You need to output $$$k$$$ numbers: the score of the game if both Alice and Bob play optimally for $$$t$$$ from $$$1$$$ to $$$k$$$.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$k$$$ ($$$1 \le k \le 20$$$) — the parameter of the size of $$$a$$$.

The second line of each test case contains $$$2^k$$$ integers $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$1 \le a_i \le 2^k$$$, $$$a_i$$$'s are pairwise distinct) — the given array $$$a$$$.

It is guaranteed that the sum of $$$2^k$$$ over all test cases does not exceed $$$2^{20}$$$.

Output

For each test case, print $$$k$$$ numbers, where the $$$i$$$-th number is the score of the game if both Alice and Bob play optimally for $$$t = i$$$.

Note

In the third test case, for $$$t = 2$$$, the game could have proceeded as follows:

Initially, $$$a = [5, 1, 6, 4, 7, 2, 8, 3]$$$.
Alice swaps $$$a_6$$$ and $$$a_8$$$, $$$a$$$ becomes $$$[5, 1, 6, 4, 7, 3, 8, 2]$$$.
Bob erases the right half of the array, $$$a$$$ becomes $$$[5, 1, 6, 4]$$$.
Alice does nothing, $$$a$$$ remains as $$$[5, 1, 6, 4]$$$.
Bob erases the right half of the array, $$$a$$$ becomes $$$[5, 1]$$$.
The game ends with a score of $$$5$$$.

Thanos Snap

Examples