Problem: D: XORANDORBAN

Problem Statement

You are given a positive integer N. Your task is to determine a set S of 2^N integers satisfying the following conditions:

* All the integers in S are at least 0  and less than 2^{N+1}.
* All the integers in S are distinct.
* You are also given three integers X, A, and O, where 0 \leq X, A, O < 2^{N+1}. Then, any two integers (a, b) in S must satisfy a {\it xor} b \neq X, a {\it and} b \neq A, a {\it or} b \neq O, where {\it xor}, {\it and}, {\it or} are bitwise xor, bitwise and, bitwise or, respectively. Note that a and b are not necessarily different.



Input


N X A O

Constraints

* 1 \leq N \leq 13
* 0 \leq X, A, O < 2^{N+1}
* Inputs consist only of integers.



Output

If there is no set satisfying the conditions mentioned in the problem statement, output `No` in a line. Otherwise, output `Yes` in the first line, and then output 2^N integers in such a set in the second line. If there are multiple sets satisfying the conditions, you can output any of them.

Sample Input 1


2 6 1 5

Output for Sample Input 1


Yes
0 3 4 7


Sample Input 2


3 0 5 1

Output for Sample Input 2


No

Sample Input 3


3 4 2 5

Output for Sample Input 3


Yes
1 0 6 15 8 9 14 7






Example

Input

2 6 1 5


Output

Yes
0 3 4 7

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

struct SCC{
    int N;
    vector<bool> used;
    vector<int> vs;
    vector<int> cmp;

    void dfs(int v, const vector<int> G[]){
        used[v] = true;
        for(auto u : G[v]){
            if(!used[u]) dfs(u, G);
        }
        vs.push_back(v);
    }

    void rdfs(int v, int k, const vector<vector<int>>& rG){
        used[v] = true;
        cmp[v] = k;
        for(auto u : rG[v]){
            if(!used[u]) rdfs(u, k, rG);
        }
    }

    SCC(int N, const vector<int> G[]):N(N){
        vector<vector<int>> rG(N);
        for(int i=0; i<N; i++) for(int j : G[i]) rG[j].push_back(i);
        used.resize(N);
        fill(used.begin(), used.end(), false);
        for(int v=0; v<N; v++){
            if(!used[v]) dfs(v, G);
        }

        fill(used.begin(), used.end(), false);
        cmp.resize(N);
        int k = 0;
        for(int i = vs.size()-1; i>=0; i--){
            if(!used[vs[i]]) rdfs(vs[i], k++, rG);
        }
    }

    int dump_graph(const vector<int> G[], vector<int> edges2[]){
        for(int i=0; i<N; i++){
            for(auto j : G[i]){
                if(cmp[i] != cmp[j]){
                    edges2[cmp[i]].push_back(cmp[j]);
                }
            }
        }
        return *max_element(cmp.begin(), cmp.end()) + 1;
    }
};

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int main(){
    int N, X, A, O;
    cin >> N >> X >> A >> O;
    int T = 1<<(N+1);
    vector<int> edges[1<<15];

    for(int i=0; i<T; i++){
        int j = i^X;
        edges[i].push_back(j+T);
        edges[j].push_back(i+T);
        edges[i+T].push_back(j);
        edges[j+T].push_back(i);
    }

    int fix = 0;
    vector<int> choice;
    const int MX = 4782969;
    static pair<int, int> memo[MX];
    for(int k=0; k<N+1; k++) if(nth_bit(A, k)){
        fix += 1<<k;
    }else{
        choice.push_back(k);
    }
    int sz = choice.size(), top = 1, K = 0;
    for(int b=0; b<pow(3, sz); b++){
        int x, y;
        if(b == 0){
            x = y = fix;
        }else{
            if(top*3 <= b){
                top *= 3;
                K++;
            }
            int q = b/top, r = b%top;
            x = memo[r].first, y = memo[r].second;
            if(q == 1) x += 1<<choice[K];
            if(q == 2) y += 1<<choice[K];
        }
        memo[b] = {x, y};
        edges[x].push_back(y+T);
        edges[y].push_back(x+T);
    }

    fix = (1<<(N+1))-1;
    choice.clear();
    for(int k=0; k<N+1; k++) if(nth_bit(O, k)){
        choice.push_back(k);
    }else{
        fix -= 1<<k;
    }
    sz = choice.size(), top = 1, K = 0;
    for(int b=0; b<pow(3, sz); b++){
        int x, y;
        if(b == 0){
            x = y = fix;
        }else{
            if(top*3 <= b){
                top *= 3;
                K++;
            }
            int q = b/top, r = b%top;
            x = memo[r].first, y = memo[r].second;
            if(q == 1) x -= 1<<choice[K];
            if(q == 2) y -= 1<<choice[K];
        }
        memo[b] = {x, y};
        edges[x].push_back(y+T);
        edges[y].push_back(x+T);
    }

    SCC scc(2*T, edges);
    vector<int> ans;
    for(int i=0; i<T; i++){
        if(scc.cmp[i] == scc.cmp[i+T]){
            cout << "No" << endl;
            return 0;
        }else if(scc.cmp[i] > scc.cmp[i+T]){
            ans.push_back(i);
        }
    }
    cout << "Yes" << endl;
    for(int i=0; i<T/2; i++) cout << ans[i] << " \n"[i==T/2-1];
    // for(int a : ans) for(int b : ans){
    //     if((a^b) == X) cerr << "X" << " " << a << " " << b << endl;
    //     if((a&b) == A) cerr << "A" << " " << a << " " << b << endl;
    //     if((a|b) == O) cerr << "O" << " " << a << " " << b << endl;
    // }
    return 0;
}