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
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
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.
Examples
input
3
1 2 3
output
No
input
6
4 7 7 12 31 61
output
Yes
4 12 7 31 7 61
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$.
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; const int MAX = 62; vector< vector<long long> > a(MAX); for (int i = 0; i < n; i++) { long long foo; cin >> foo; int highest = -1; for (int j = MAX - 1; j >= 0; j--) { if (foo & (1LL << j)) { highest = j; break; } } a[highest].push_back(foo); } vector<long long> res; for (int j = MAX - 1; j >= 0; j--) { if (a[j].empty()) { continue; } vector<long long> new_res; new_res.push_back(a[j].back()); a[j].pop_back(); for (long long foo : res) { new_res.push_back(foo); if (foo & (1LL << j)) { if (!a[j].empty()) { new_res.push_back(a[j].back()); a[j].pop_back(); } } } if (!a[j].empty()) { cout << "No" << '\n'; return 0; } swap(res, new_res); } cout << "Yes" << '\n'; for (int i = 0; i < n; i++) { if (i > 0) { cout << ' '; } cout << res[i]; } cout << '\n'; return 0; }