#include<iostream>

using namespace std;

class BST
{
    struct node
    {
        int data;
        node* left;
        node* right;
        int height;
    };

    node* root;

    void makeEmpty(node* t)
    {
        if(t == NULL)
            return;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }

    node* insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->height = 0;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
        {
            t->left = insert(x, t->left);
            if(height(t->left) - height(t->right) == 2)
            {
                if(x < t->left->data)
                    t = singleRightRotate(t);
                else
                    t = doubleRightRotate(t);
            }
        }
        else if(x > t->data)
        {
            t->right = insert(x, t->right);
            if(height(t->right) - height(t->left) == 2)
            {
                if(x > t->right->data)
                    t = singleLeftRotate(t);
                else
                    t = doubleLeftRotate(t);
            }
        }

        t->height = max(height(t->left), height(t->right))+1;
        return t;
    }

    node* singleRightRotate(node* &t)
    {
        node* u = t->left;
        t->left = u->right;
        u->right = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(u->left), t->height)+1;
        return u;
    }

    node* singleLeftRotate(node* &t)
    {
        node* u = t->right;
        t->right = u->left;
        u->left = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(t->right), t->height)+1 ;
        return u;
    }

    node* doubleLeftRotate(node* &t)
    {
        t->right = singleRightRotate(t->right);
        return singleLeftRotate(t);
    }

    node* doubleRightRotate(node* &t)
    {
        t->left = singleLeftRotate(t->left);
        return singleRightRotate(t);
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* remove(int x, node* t)
    {
        node* temp;


        if(t == NULL)
            return NULL;


        else if(x < t->data)
            t->left = remove(x, t->left);
        else if(x > t->data)
            t->right = remove(x, t->right);


        else if(t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }

        else
        {
            temp = t;
            if(t->left == NULL)
                t = t->right;
            else if(t->right == NULL)
                t = t->left;
            delete temp;
        }
        if(t == NULL)
            return t;

        t->height = max(height(t->left), height(t->right))+1;


        if(height(t->left) - height(t->right) == 2)
        {

            if(height(t->left->left) - height(t->left->right) == 1)
                return singleLeftRotate(t);

            else
                return doubleLeftRotate(t);
        }
        else if(height(t->right) - height(t->left) == 2)
        {
            if(height(t->right->right) - height(t->right->left) == 1)
                return singleRightRotate(t);
            else
                return doubleRightRotate(t);
        }
        return t;
    }

    int height(node* t)
    {
        return (t == NULL ? -1 : t->height);
    }

    int getBalance(node* t)
    {
        if(t == NULL)
            return 0;
        else
            return height(t->left) - height(t->right);
    }

    void inorder(node* t)
    {
        if(t == NULL)
            return;
        cout << t->data;
        inorder(t->left);

        inorder(t->right);
    }

public:
    BST()
    {
        root = NULL;
    }

    void insert(int x)
    {
        root = insert(x, root);
    }

    void remove(int x)
    {
        root = remove(x, root);
    }

    void display()
    {
        inorder(root);
        cout << endl;
    }
};

int main()
{
    BST t;
    int liczba;

    t.insert(12);
    t.insert(6);
    t.insert(3);
    t.insert(1);
    t.insert(4);
    t.insert(8);
    t.insert(7);
    t.insert(10);
    t.insert(62);
    t.insert(26);
    t.insert(14);
    t.insert(29);
    t.insert(104);
    t.insert(69);
    cin >> liczba;
    t.remove(liczba);
    t.display();
}
/*
#include <iostream>
#include <cstdio>
#include <string>
#include <malloc.h>
#include <cstdlib>

using namespace std;

struct drzewoAVL{
    int liczba;
    int wysokosc;
    struct drzewoAVL* lewy;
    struct drzewoAVL* prawy;
};

typedef drzewoAVL* AVL;

void insert(AVL &wezel, int liczba)
{
    if(wezel == NULL)
    {
        wezel = new drzewoAVL();
        wezel->prawy = wezel->lewy = NULL;
        wezel->liczba = liczba;
        wezel->wysokosc = 0;
    }
    else if(liczba < wezel->liczba)
    {
        insert(wezel->lewy, liczba);
    }
    else if(liczba > wezel->liczba)
    {
        insert(wezel->prawy,liczba);
    }
}
void preOrder(AVL wezel)
{
    if(wezel)
    {
        cout << wezel->liczba << " ";
        preOrder(wezel->lewy);
        preOrder(wezel->prawy);
    }
}

AVL rotacjaPrawo(AVL wezel)
{
    AVL dzieckoL = wezel->lewy;
    wezel->lewy = dzieckoL->prawy;
    dzieckoL->prawy = wezel;

    if(wezel->lewy->wysokosc > wezel->prawy->wysokosc)
    {
        wezel->wysokosc = wezel->lewy->wysokosc + 1;
    }
    else
    {
        wezel->wysokosc = wezel->prawy->wysokosc + 1;
    }
    if(dzieckoL->lewy->wysokosc > dzieckoL->prawy->wysokosc)
    {
        dzieckoL->wysokosc = dzieckoL->lewy->wysokosc + 1;
    }
    else
    {
        dzieckoL->wysokosc = dzieckoL->prawy->wysokosc + 1;
    }
    return dzieckoL;
}
AVL rotacjaLewo(AVL wezel)
{
    AVL dzieckoR = wezel->prawy;
    wezel->prawy = dzieckoR->lewy;
    dzieckoR->lewy = wezel;

    if(wezel->lewy->wysokosc > wezel->prawy->wysokosc)
    {
        wezel->wysokosc = wezel->lewy->wysokosc + 1;
    }
    else
    {
        wezel->wysokosc = wezel->prawy->wysokosc + 1;
    }
    if(dzieckoR->lewy->wysokosc > dzieckoR->prawy->wysokosc)
    {
        dzieckoR->wysokosc = dzieckoR->lewy->wysokosc + 1;
    }
    else
    {
        dzieckoR->wysokosc = dzieckoR->prawy->wysokosc + 1;
    }
    return dzieckoR;
}
drzewoAVL usunWezel(AVL wezel, int liczba)
{
    if(wezel)
    {
        if(liczba == wezel->liczba)
        {
            AVL _temp = wezel;
            if((wezel->prawy && wezel->lewy)==NULL)
            {
                free(wezel);
            }
            if(wezel->prawy && !wezel->lewy)
            {

            }



        }
        if(liczba < wezel->liczba)
        {
            usunWezel(wezel->lewy, liczba);
        }
        if(liczba > wezel->liczba)
        {
            usunWezel(wezel->prawy, liczba);
        }

    }
}
int main() {
    AVL korzen = NULL;
    int usun;

    insert(korzen, 12);
    insert(korzen, 6);
    insert(korzen, 3);
    insert(korzen, 1);
    insert(korzen, 4);
    insert(korzen, 8);
    insert(korzen, 7);
    insert(korzen, 10);
    insert(korzen, 62);
    insert(korzen, 26);
    insert(korzen, 14);
    insert(korzen, 29);
    insert(korzen, 12);
    insert(korzen, 104);
    insert(korzen, 69);

    cin >> usun;
    usunWezel(korzen, usun);
    preOrder(korzen);

    return 0;
}
*/