← 返回题目列表

Codeforces · 1742/G

G. 奥雷

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 个非负整数。

让我们将前缀 OR 数组 $$$b$$$ 定义为数组 $$$b_i = a_1~\mathsf{OR}~a_2~\mathsf{OR}~\dots~\mathsf{OR}~a_i$$$,其中 $$$\mathsf{OR}$$$ 表示按位 OR 运算。换句话说,数组$$$b$$$是通过计算$$$a$$$的每个前缀的$$$\mathsf{OR}$$$而形成的。

系统要求您重新排列数组 $$$a$$$ 的元素,使其前缀 OR 数组按字典顺序最大。

如果在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,$$$x_i > y_i$$$,则数组 $$$x$$$ 按字典顺序大于数组 $$$y$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 非负整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例打印 $$$n$$$ 整数 - 数组 $$$a$$$ 的任何重新排列,以获得按字典顺序排列的最大前缀 OR 数组。

示例

输入 #1

5
4
1 2 4 8
7
5 1 2 3 4 5 5
2
1 101
6
2 3 4 2 3 4
8
1 4 2 3 4 5 7 1

输出 #1

8 4 2 1 
5 2 1 3 4 5 5 
101 1 
4 3 2 2 3 4 
7 1 4 2 3 4 5 1