Big Secret
Contest: VK Cup 2018 - Round 3
Difficulty rating: 2200
Tags: constructive algorithms, math

Vitya has learned that the answer for The Ultimate Question of Life, the Universe, and Everything is not the integer 54 42, but an increasing integer sequence $$$a_1, \ldots, a_n$$$. In order to not reveal the secret earlier than needed, Vitya encrypted the answer and obtained the sequence $$$b_1, \ldots, b_n$$$ using the following rules:

- $$$b_1 = a_1$$$;
- $$$b_i = a_i \oplus a_{i - 1}$$$ for all $$$i$$$ from 2 to $$$n$$$, where $$$x \oplus y$$$ is the bitwise XOR of $$$x$$$ and $$$y$$$.

It is easy to see that the original sequence can be obtained using the rule $$$a_i = b_1 \oplus \ldots \oplus b_i$$$.

However, some time later Vitya discovered that the integers $$$b_i$$$ in the cypher got shuffled, and it can happen that when decrypted using the rule mentioned above, it can produce a sequence that is not increasing. In order to save his reputation in the scientific community, Vasya decided to find some permutation of integers $$$b_i$$$ so that the sequence $$$a_i = b_1 \oplus \ldots \oplus b_i$$$ is strictly increasing. Help him find such a permutation or determine that it is impossible.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ ($$$1 \leq b_i < 2^{60}$$$).

Output format:
If there are no valid permutations, print a single line containing "No".

Otherwise in the first line print the word "Yes", and in the second line print integers $$$b'_1, \ldots, b'_n$$$ — a valid permutation of integers $$$b_i$$$. The unordered multisets $$$\{b_1, \ldots, b_n\}$$$ and $$$\{b'_1, \ldots, b'_n\}$$$ should be equal, i. e. for each integer $$$x$$$ the number of occurrences of $$$x$$$ in the first multiset should be equal to the number of occurrences of $$$x$$$ in the second multiset. Apart from this, the sequence $$$a_i = b'_1 \oplus \ldots \oplus b'_i$$$ should be strictly increasing.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example no permutation is valid.

In the second example the given answer lead to the sequence $$$a_1 = 4$$$, $$$a_2 = 8$$$, $$$a_3 = 15$$$, $$$a_4 = 16$$$, $$$a_5 = 23$$$, $$$a_6 = 42$$$.

Example input:
3
1 2 3

Example output:
No

Example input:
6
4 7 7 12 31 61

Example output:
Yes
4 12 7 31 7 61

Editorial:
Let's assume that we've found a suitable permutation of all numbers, except all occurences of the number $$$1$$$. When can we insert the $$$1$$$'s so that the new arrangement of numbers is again good? We can see that the XOR of all numbers before any occurence of the number $$$1$$$ must be even, so there should an even number of odd numbers before it.
Suppose that there are $$$x$$$ $$$1$$$'s in the input, and $$$y$$$ odd numbers greater than $$$1$$$. If $$$x > y + 1$$$, then in any arrangement there is going to be a pair of $$$1$$$'s such that there are no odd numbers between them, hence the condition above cannot hold for both of them simultaneously. On the other hand, if $$$x \leq y + 1$$$, then it is possible to insert the $$$1$$$'s into any permutation of greater numbers. Indeed, we can place one instance of $$$1$$$ at the start, and then place remaining $$$1$$$'s immediately after greater odd numbers.
Note that this argument works just as well if we consider numbers in the range $$$[2^k, 2^{k + 1})$$$ as "$$$1$$$'s", and numbers in $$$[2^{k + 1}, \infty)$$$ as "numbers greater than $$$1$$$". Note further that it doesn't matter how exactly we insert the "$$$1$$$'s" since number of available gaps doesn't depend on that. Hence, we can go as follows: group the numbers by their leading bits. Make an empty list for the answer, and process the numbers in groups by decreasing of their leading bits. Suppose there are $$$x$$$ numbers with leading bit $$$k$$$, and $$$y$$$ greater numbers that have $$$1$$$ in the $$$k$$$-th bit. If $$$x > y + 1$$$, then there is no answer. Otherwise, insert the numbers from the current group as described above.
The complexity of this solution is $$$O(n \log A)$$$, where $$$A$$$ is the largest value among the numbers in the input.