Codeforces 976E/925C （01Trie树）

题面：

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}, \dots, a_{n}$

. In order to not reveal the secret earlier than needed, Vitya encrypted the answer and obtained the sequence

b_{1}, \dots, 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 \dots \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 \dots \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}, \dots, 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}^{'}, \dots, b_{n}^{'}$

— a valid permutation of integers

b_{i}

. The unordered multisets

{b_{1}, \dots, b_{n}}

and

{b_{1}^{'}, \dots, 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 \dots \oplus b_{i}^{'}

should be strictly increasing.

If there are multiple answers, print any of them.

Examples

Input

Copy

3
1 2 3

Output

Copy

No

Input

Copy

6
4 7 7 12 31 61

Output

Copy

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

题目描述：给你一个n个数的数列，问你是否可以使数列中的某些元素调换，使得新数列满足，Ai=（B1 xor B2 xor...Bi）严格单调递增。

题目分析：因为这道题所要我们求的是异或和递增，我们不妨从最终的异或和开始倒推，每次都让他递减，那我们就可以贪心的选择减少得最少的。

而因为这题我们维护的是异或和，因此我们可以通过Trie树进行维护。

具体的做法是，我们从最高位往地位去枚举，如果当前的位数为s=1，则无论x取0还是1都会使得最终的s变小，而我们希望减少量不至于太大，因此我们优先考虑x=0的情况，如果找不到x=1，再考虑x=0的情况。

如果当前的位数s=0，则如果我们取x=1，会使得s在这一位上变大，这种操作只在高位存在s从1变成0的情况下才能够成立，如果成立，则从减少变化量的角度来讲，则优先得从x=0来考虑，x=1找不到再找x=0的。

整体是的做法就类似与在Trie树上去做一趟数位dp，不断寻找符合条件的数，最后存储即可。

具体可以看一下代码

#include <bits/stdc++.h>
#define maxn 6000005
using namespace std;
typedef long long ll;
int n;
struct Trie{
    int trie[maxn][2];//trie树
    int cnt[maxn];//每个节点所经过的数量
    int root=0;//根
    ll val[maxn];//中断点的坐标
    ll xorsum=0;//异或和
    ll ans[maxn/10];//答案
    int C=0;
    int newroot(){//新开结点
        trie[C][0]=trie[C][1]=-1;
        cnt[C]=0;
        return C++;
    }
    void Insert(ll x){//trie树的插入
        ll p=root;
        for(int i=60;i>=0;i--){
            ll id=(x>>i)&1;
            if(trie[p][id]==-1) trie[p][id]=newroot();
            p=trie[p][id];
            cnt[p]++;
        }
        val[p]=x;
    }
    bool check(ll xorsum,ll &res,int index,bool limit,int dep){//limit代表前一位是否有从1变为0的情况,dep代表深度
        if(index!=root&&(cnt[index]==0||index==-1)) return false;
        if(dep==-1){//深度为-1证明完全满足条件，则最终结果为val[index]
            res=val[index];
            cnt[index]--;
            return true;
        }
        int id=(xorsum>>dep)&1;//获取当前异或和的深度的位数
        if(id==0){//判断当前位为0
            bool ret=(check(xorsum,res,trie[index][0],limit,dep-1))||
            (!limit&&check(xorsum,res,trie[index][1],limit,dep-1));
            if(ret==0) return false;
            cnt[index]--;
            return true;
        }
        else{//判断当前位为1的情况
            bool ret=(check(xorsum,res,trie[index][0],limit,dep-1))||
            (check(xorsum,res,trie[index][1],false,dep-1));
            if(ret==0) return false;
            cnt[index]--;
            return true;
        }
    }
    void solve(){
        for(int i=n-1;i>=0;i--){
            ll res;
            bool ret=check(xorsum,res,root,true,60);
            if(ret==0){
                puts("No");
                return;
            }
            ans[i]=res;
            assert(xorsum>(xorsum^res));
            xorsum^=res;
        }
        puts("Yes");
        for(int i=0;i<n;i++){
            cout<<ans[i]<<" ";
        }
        puts("");
    }
}Tree;
int main()
{
    scanf("%d",&n);
    Tree.root=Tree.newroot();
    for(int i=0;i<n;i++){
        ll x;
        scanf("%I64d",&x);
        Tree.Insert(x);
        Tree.xorsum^=x;
    }
    Tree.solve();
}