311222: CF1951H. Thanos Snap

H. Thanos Snaptime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputPiotr 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$.

ExampleInput

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

Output

1
3 1
7 5 1
15 13 9 1
31 28 25 17 1

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$.

题目大意：
这是一个关于数组a的游戏，a的大小为2的k次方，初始时a是1到2的k次方的全排列。Alice和Bob轮流在数组a上进行操作。首先，他们会看到1到k之间的一个值t。然后，接下来的t轮，每一轮：

- Alice可以选择不操作，或者选择数组a中的两个不同的元素并交换它们。
- Bob可以选择数组a的左半部分或右半部分并删除它。

游戏的得分定义为所有t轮操作结束后数组a中的最大值。Alice希望最大化这个得分，而Bob希望最小化它。

你需要输出k个数字：如果Alice和Bob在t从1到k时都进行最优操作，游戏的得分。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数k（1≤k≤20）——数组a的大小参数。

每个测试用例的第二行包含2^k个整数a1, a2, ..., a2^k（1≤ai≤2^k，ai两两不同）——给定的数组a。

保证所有测试用例的2^k之和不超过2^20。

输出数据格式：
对于每个测试用例，输出k个数字，其中第i个数字是如果Alice和Bob在t=i时都进行最优操作，游戏的得分。题目大意： 这是一个关于数组a的游戏，a的大小为2的k次方，初始时a是1到2的k次方的全排列。Alice和Bob轮流在数组a上进行操作。首先，他们会看到1到k之间的一个值t。然后，接下来的t轮，每一轮： - Alice可以选择不操作，或者选择数组a中的两个不同的元素并交换它们。 - Bob可以选择数组a的左半部分或右半部分并删除它。 游戏的得分定义为所有t轮操作结束后数组a中的最大值。Alice希望最大化这个得分，而Bob希望最小化它。 你需要输出k个数字：如果Alice和Bob在t从1到k时都进行最优操作，游戏的得分。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数k（1≤k≤20）——数组a的大小参数。 每个测试用例的第二行包含2^k个整数a1, a2, ..., a2^k（1≤ai≤2^k，ai两两不同）——给定的数组a。 保证所有测试用例的2^k之和不超过2^20。 输出数据格式： 对于每个测试用例，输出k个数字，其中第i个数字是如果Alice和Bob在t=i时都进行最优操作，游戏的得分。