1742G.md (1640B)
1 Source: https://codeforces.com/problemset/problem/1742/G 2 3 G. Orray 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ consisting of $n$ nonnegative integers. 22 23 Let's define the prefix OR array $b$ as the array $b_i = a_1~\mathsf{OR}~a_2~\mathsf{OR}~\dots~\mathsf{OR}~a_i$, where $\mathsf{OR}$ represents the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). In other words, the array $b$ is formed by computing the $\mathsf{OR}$ of every prefix of $a$. 24 25 You are asked to rearrange the elements of the array $a$ in such a way that its prefix OR array is lexicographically maximum. 26 27 An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ, $x_i \gt y_i$. 28 29 Input 30 31 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$. 34 35 The second line of each test case contains $n$ nonnegative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq 10^9$). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case print $n$ integers — any rearrangement of the array $a$ that obtains the lexicographically maximum prefix OR array. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 4 51 52 1 2 4 8 53 54 7 55 56 5 1 2 3 4 5 5 57 58 2 59 60 1 101 61 62 6 63 64 2 3 4 2 3 4 65 66 8 67 68 1 4 2 3 4 5 7 1 69 ``` 70 71 Output 72 73 ``` 74 8 4 2 1 75 5 2 1 3 4 5 5 76 101 1 77 4 3 2 2 3 4 78 7 1 4 2 3 4 5 1 79 ```