#include <iostream>
#include <fstream>
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"

using namespace std;

fstream infile, outfile;

template <class H>
class Nodo
{
    private:
        H val;
        Nodo<H> *sinistro, *destro, *padre;
    public:
        Nodo(H v, Nodo<H>* p=0, Nodo<H>* s=0, Nodo<H>* d=0) :
        val(v), padre(p), sinistro(s), destro(d) {}
        void setVal(H v)
        {
            val = v;
        }
        void setLeft(Nodo<H>* s)
        {
            sinistro = s;
        }
        void setRight(Nodo<H>* d)
        {
            destro = d;
        }
        void setPadre(Nodo<H>* p)
        {
            padre = p;
        }
        H getVal()
        {
            return val;
        }
        Nodo<H>* getLeft()
        {
            return sinistro;
        }
        Nodo<H>* getRight()
        {
            return destro;
        }
        Nodo<H>* getPadre()
        {
            return padre;
        }
};

template <class H>
class BST
{
    private:
        Nodo<H>* root;
        void _printPreOrder(Nodo<H>* n);
        void _printInOrder(Nodo<H>* n);
        void _printPostOrder(Nodo<H>* n);
        Nodo<H>* _min(Nodo<H>* n);
        Nodo<H>* _search(H val);
        void _remove(Nodo<H>* n);
    public:
        BST():root(0) {}
        BST<H>* insert(H val);
        BST<H>* printInOrder();
        BST<H>* printPreOrder();
        BST<H>* printPostOrder();
        H min();
        bool search(H val);
        BST<H>* remove(H val);
};

template <class H>
BST<H>* BST<H>::insert(H val)
{
    if (root==0)
        root = new Nodo<H>(val);
    else
    {
        Nodo<H>* aux = root;
        bool inserted = false;
        while (!inserted)
        {
            if (val>aux->getVal())
            {
                if (aux->getRight()==0)
                {
                    aux->setRight(new Nodo<H>(val, aux));
                    inserted = true;
                }
                else
                    aux = aux->getRight();
            }
            else
            {
                if (aux->getLeft()==0)
                {
                    aux->setLeft(new Nodo<H>(val, aux));
                    inserted = true;
                }
                else
                    aux = aux->getLeft();
            }
        }
    }
    return this;
}

template <class H>
void BST<H>::_printPreOrder (Nodo<H>* aux)
{
    if (aux!=0)
    {
        outfile << aux->getVal() << " ";
        _printPreOrder(aux->getLeft());
        _printPreOrder(aux->getRight());
    }

}
template <class H>
void BST<H>::_printInOrder (Nodo<H>* aux)
{
    if (aux!=0)
    {
        _printInOrder(aux->getLeft());
        outfile << aux->getVal() << " ";
        _printInOrder(aux->getRight());
    }

}
template <class H>
void BST<H>::_printPostOrder (Nodo<H>* aux)
{
    if (aux!=0)
    {
        _printPostOrder(aux->getLeft());
        _printPostOrder(aux->getRight());
        outfile << aux->getVal() << " ";
    }

}
template <class H>
BST<H>* BST<H>::printPreOrder()
{
    _printPreOrder(root);
    return this;
}
template <class H>
BST<H>* BST<H>::printInOrder()
{
    _printInOrder(root);
    return this;
}
template <class H>
BST<H>* BST<H>::printPostOrder()
{
    _printPostOrder(root);
    return this;
}

template <class H>
Nodo<H>* BST<H>::_min(Nodo<H>* r)
{
    if (r==0)
        return 0;
    while (r->getLeft())
        r=r->getLeft();
    return r;
}
template <class H>
H BST<H>::min()
{
    Nodo<H>* aux = _min(root);
    if (aux)
        return aux->getVal();
    else
        return -99999;
}

template <class H>
Nodo<H>* BST<H>::_search(H val)
{
    Nodo<H>* aux = root;
    while (aux != 0)
    {
        if (val > aux->getVal())
            aux = aux->getRight();
        else if (val < aux->getVal())
            aux = aux->getLeft();
        else
            return aux;
    }
    return 0;
}
template <class H>
bool BST<H>::search(H val)
{
    if (_search(val)==0)
        return false;
    else
        return true;
}

template <class H>
void BST<H>::_remove(Nodo<H>* n)
{
    if (n == 0)
        return;

    if (n->getLeft()==0 && n->getRight()==0)
    {
        Nodo<H>* padre = n->getPadre();
        if (padre!=0)
        {
            if (padre->getRight()==n)
                padre -> setRight(0);
            else
                padre -> setLeft(0);
        }
        else
            root = 0;

        delete n;
        return;
    }

    if (n->getLeft()==0 ^ n->getRight()==0)
    {
        Nodo<H>* padre = n->getPadre();
        if (n->getLeft()!=0)
        {
            if (padre != 0)
            {
                if (padre->getLeft()==n)
                    padre->setLeft(n->getLeft());
                else
                    padre->setRight(n->getLeft());
                n->getLeft()->setPadre(padre);
            }
            else
                root = n->getLeft();
        }
        else
        {
            if (padre!=0)
            {
                if (padre->getLeft()==n)
                    padre->setLeft(n->getRight());
                else
                    padre->setRight(n->getRight());
                n->getRight()->setPadre(padre);
            }
            else
                root = n->getRight();
        }
        delete n;
        return;
    }
    Nodo<H>* minimo = _min(n->getRight());
    n->setVal(minimo->getVal());
    _remove(minimo);
}
template <class H>
BST<H>* BST<H>::remove(H val)
{
    _remove(_search(val));
    return this;
}

int getDuePunti(string x)
{
    for (int i=0; i<x.length(); i++)
        if (x[i]==':')
            return i;
    return 0;
}

string getOp(string x)
{
    return x.substr(0, getDuePunti(x));
}

string getValore(string x)
{
    return x.substr(getDuePunti(x)+1, x.length());
}

int main()
{
    infile.open(INPUT_FILE, fstream::in);
    outfile.open(OUTPUT_FILE, fstream::out);

    for (int k=0; k<100; k++)
    {
        string tipo, ordine;
        int N;
        infile >> tipo;
        if (tipo=="int")
        {
            infile >> N >> ordine;
            BST<int>* tree = new BST<int>;
            for (int i=0; i<N; i++)
            {
                string oper;
                string tmp;
                string _valore;
                int n;
                infile >>tmp;
                oper = getOp(tmp);
                _valore = getValore(tmp);
                n = stoi(_valore);

                if(oper=="ins")
                    tree->insert(n);
                else if (oper=="canc")
                    tree->remove(n);

                if (ordine=="preorder")
                    tree->printPreOrder();
                else if (ordine=="inorder")
                    tree->printInOrder();
                else if (ordine=="postorder")
                    tree->printPostOrder();
            }
        }
        else if (tipo=="double")
        {
            infile >> N >> ordine;
            BST<double>* tree = new BST<double>;
            for (int i=0; i<N; i++)
            {
                string oper;
                string tmp;
                string _valore;
                double n;
                infile >>tmp;
                oper = getOp(tmp);
                _valore = getValore(tmp);
                n = stod(_valore);

                if(oper=="ins")
                    tree->insert(n);
                else if (oper=="canc")
                    tree->remove(n);
                if (ordine=="preorder")
                    tree->printPreOrder();
                else if (ordine=="postorder")
                    tree->printPostOrder();
                else if (ordine == "inorder")
                    tree->printInOrder();
            }
        }
        outfile << endl;
    }
    infile.close();
    outfile.close();
}