struct Node
{
    int key;
    int bit;
    Node *next[2];
    Node() { }
};

class PATRICIA
{
public:
    Node *root;
    PATRICIA()
    {
        root = new Node();
        root->key = 0;
        root->bit = 0;
        root->next[0] = root->next[1] = root;
    }
    int bit(int x, int i)
    {
        return (x >> i) & 1;
    }
    Node *Search(int v)
    {
        Node *p = root;
        Node *pp = NULL;
        do
        {
            pp = p;
            p = p->next[bit(v, p->bit)];
        } while (pp->bit > p->bit);
        return p;
    }
    void Insert(int v)
    {
        Node *q = Search(v);
        if (q->key == v) return;
        int b = MAX;
        for (; bit(v, b) == bit(q->key, b); b--);

        Node *p = root;
        Node *pp = NULL;
        do
        {
            pp = p;
            p = p->next[bit(v, p->bit)];
        } while (pp->bit > p->bit && p->bit > b);

        q = new Node();
        q->key = v;
        q->bit = b;
        q->next[bit(v, b)] = q;
        q->next[1 - bit(v, b)] = p;
        pp->next[bit(v, pp->bit)] = q;
    }
    void PrintRec(Node *p)
    {
        if(p)
        {
            if (p->next[0]->bit < p->bit) PrintRec(p->next[0]);
            cout << p->key << " ";
            if (p->next[1]->bit < p->bit) PrintRec(p->next[1]);
        }
    }
    void Print()
    {
        PrintRec(root);
        cout << endl;
    }
};