对于某个正整数 $$$k$$$,有一个大小为 $$$2^k$$$ 的数组 $$$a$$$,它最初是从 $$$1$$$ 到 $$$2^k$$$ 的值的排列。 Alice 和 Bob 在数组 $$$a$$$ 上玩以下游戏。首先,向 Alice 和 Bob 显示 $$$1$$$ 和 $$$k$$$ 之间的值 $$$t$$$。然后,对于 $$$t$$$ 轮,会发生以下情况:
- Alice 要么不执行任何操作,要么选择数组 $$$a$$$ 中的两个不同元素并交换它们。
- Bob 选择数组 $$$a$$$ 的左半部分或右半部分并将其删除。
游戏得分定义为玩完所有 $$$t$$$ 回合后 $$$a$$$ 中的最大值。 Alice 想要最大化这个分数,而 Bob 想要最小化它。
您需要输出 $$$k$$$ 数字:如果 Alice 和 Bob 都在 $$$1$$$ 到 $$$k$$$ 之间以最佳状态玩 $$$t$$$,则游戏的分数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$ 数字是如果 Alice 和 Bob 都以最佳状态玩 $$$t = i$$$ 时的游戏得分。
示例
输入 #1
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
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]$$$。
- Alice 交换 $$$a_6$$$ 和 $$$a_8$$$,$$$a$$$ 变成 $$$[5, 1, 6, 4, 7, 3, 8, 2]$$$。
- Bob 删除了数组的右半部分,$$$a$$$ 变为 $$$[5, 1, 6, 4]$$$。
- Alice 没有执行任何操作,$$$a$$$ 仍为 $$$[5, 1, 6, 4]$$$。
- Bob 删除了数组的右半部分,$$$a$$$ 变为 $$$[5, 1]$$$。
- 游戏以 $$$5$$$ 得分结束。