/**
 * By:   Asif Ahmed
 * TODO: Proposed optimization.
 */



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

#define TOTALBITS 16
#define N 20000


typedef struct alist anode;
struct alist{
    int val_count;
    int val;
};

typedef struct bstree bnode;
struct bstree{
    int bit;
    bnode *left;
    bnode *right;
    anode *p;
};


int executionCount = 0;
void printGivenLevel(bnode* root, int level)
{
    ++executionCount;
    if (root == NULL)
        return;
    if (level == 1){
        int c = root->p->val_count;
        for(int i = 0; i < c; ++i){
            printf("%d ", root->p->val);
        }
    }
    else
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}


int main(){


    int modVal = pow(2, TOTALBITS);
    int unsorted[N];
    for(int i = 0; i < N; ++i){
        unsorted[i] = rand() % modVal;
    }



    // create R root
    bnode *R;
    R = new bnode();


    // access inside main
    anode* aroot;


    // For the first time this is needed but can be avoided
    if(unsorted[0]){
        //cout << S << endl;

        // create anode beforehand for the first time
        aroot = new anode();
        aroot->val = unsorted[0];
        aroot->val_count = 1;

        // create temp root
        bnode* r = R;
        int val = unsorted[0];

        // For each of the bits create node and connect to tree
        for(int i = TOTALBITS - 1; i >= 0; --i){
            bnode *temp = new bnode();
            temp->bit = (val >> i) & 1;
            temp->p = aroot;
            if(temp->bit){
                r->right = temp;
            }else{
                r->left = temp;
            }
            r = temp;
        }
        r->left = NULL;
        r->right = NULL;
    }


    // hold bottom level alist root in a temporary root
    anode *arootTemp = aroot;
    anode *an;


    // For all other inputs
    for(int j = 1; j < N; ++j){
//printf("%d ", unsorted[j]);
        // create temp root
        bnode* r = R;

        //
        bool createOnce = true;
        //
        //cout << "==================\n";
        //cout << "USING: " << S << "\n";

        int val = unsorted[j];

        //printf("FOR:: %d\n", val);
        int x = 0;

        // For each of the bits create node and connect to tree
        for(int i = TOTALBITS - 1; i >= 0; --i){
            int m = (val >> i) & 1;
            //cout << "USING BIT: " << ((val >> i) & 1)  << "\n";

            // If bit is zero then go left otherwise go right
            if( m ){
                if(r->right != NULL){
                    //cout << "FOLLOWING LAID OUT PATH RIGHT: " << "\n";
                    r = r->right;
                    ++x;
                }else{
                    x = 0;
                    //cout << "CREATING NEW NODE RIGHT: " << "\n";
                    if(createOnce){
                        an = new anode();
                        an->val = unsorted[j];
                        an->val_count = 1; // If this is done it acts as a set
                        createOnce = false;
                    }
                    bnode *tmp = new bnode();
                    tmp->bit = m;
                    tmp->left = NULL;
                    tmp->right = NULL;
                    tmp->p = an;

                    // now mark tmp as the new r
                    r->right = tmp;
                    r = tmp;
                }
            }else{
                if(r->left != NULL){
                    //cout << "FOLLOWING LAID OUT PATH LEFT: " << "\n";
                    r = r->left;
                    ++x;
                }else{
                    x = 0;
                    //cout << "CREATING NEW NODE LEFT: " << "\n";
                    if(createOnce){
                        an = new anode();
                        an->val = unsorted[j];
                        an->val_count = 1; // If this is done it acts as a set
                        createOnce = false;
                    }
                    bnode *tmp = new bnode();
                    tmp->bit = m;
                    tmp->left = NULL;
                    tmp->right = NULL;
                    tmp->p = an;

                    // now mark tmp as the new r
                    r->left = tmp;
                    r = tmp;
                }
            }
        }

        if(x == TOTALBITS){
            r->p->val_count = r->p->val_count + 1;
        }
    }
   // printf("===================\nDone\n===================\n");


    // now run DFS to sort
    // r is a node* that was defined above


    /**
     * UNCOMMENT LINES BELOW TO PRINT SET RESULT.
     */

    bnode* r;
    r = R->left;
    printGivenLevel(r, TOTALBITS);
    r = R->right;
    printGivenLevel(r, TOTALBITS);



    //printf("\n===========================================\n");
    //printf("\nLOOP EXECUTION COUNT: %d \n", executionCount);

    return 0;
}