荒坂潜码行动

题目描述

2077年的夜之城，整个网络空间被荒坂（Arasaka）构筑的 量子分段防火墙 所统治。

这套防火墙将内存地址划分为 ($2^N$) 个 网格节点（Grid Node），每个节点中存放一个编号唯一的 数据块 DataBlock ，构成一个排列：

$P=(P_0,P_1,\ldots,P_{2^N-1})$

你是一名传说级网潜者（Netrunner）。

你的任务是——在不触发荒坂 ICE（入侵对抗实体） 的前提下，通过特定的黑客指令，重构这段数据，使之达到字典序最小，从而成功躲避扫描、潜入更深层的黑网。

你掌握一种不会触发 ICE 的隐蔽操作：

• 选取整数 ($a,b$)（均可为 0），但必须满足： $0 \le a \cdot 2^b < (a+1)\cdot 2^b \le 2^N$
• 然后把区间 ($[a\cdot 2^b, (a+1)\cdot 2^b-1]$) 里的数据块整体反转。

这相当于你能翻转任意一个 长度为 ($2^b$) 的内存子段。 荒坂防火墙的结构使得只有长度为 2 的幂 的块才不会触发警报。

比如：

• b=0 → 翻转长度 1（啥都不变）
• b=1 → 翻转长度 2
• b=2 → 翻转长度 4
• ……

你可以进行任意多次操作（包括 0 次）。

你的目标—— 让最终排列成为 所有可达状态中字典序最小的序列。

输入格式

你将收到来自委托人的加密数据：

• 第一行：测试组数 T(1 ≤ T ≤ 10^4)

• 每组数据提供：

  • 一个整数 N (1 ≤ N ≤ 19)
  • 一个长度为 $2^N$ 的排列

输出格式

对每组数据，输出你能达到的 字典序最小结果。

样例 1

3
1
1 2
2
1 3 4 2
2
2 3 4 1

1 2
1 3 2 4
1 4 2 3

提示

在第一个测试案例中，当没有对 $P$ 进行操作时， $P=(1,2)$ 。这是词法上最小的排列。因此，答案是 $(1,2)$ 。

在第二个测试案例中，当我们对 $a=1,b=1$ 进行操作时， $P$ 变成了 $(1,3,2,4)$ 。无论我们对 $P$ 进行多少次运算，都无法得到一个在词序上小于 $(1,3,2,4)$ 的排列。因此，答案是 $(1,3,2,4)$ 。

在第三个测试案例中，按照以下顺序进行运算，我们可以得到 $P=(1,4,2,3)$ ：

• 执行与 $a=0,b=1$ 的运算。 $P$ 变为 $(3,2,4,1)$ 。
• 与 $a=0,b=2$ 进行运算。 $P$ 变为 $(1,4,2,3)$ 。

无论我们对 $P$ 进行多少次运算，都无法得到一个在词序上小于 $(1,4,2,3)$ 的排列。因此，答案是 $(1,4,2,3)$ 。