#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,tip,value;

struct Node
{
    int value;
    struct Node *left, *right;
	int height;
} *Root, *NIL;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

void init()
{
    Root = NIL = (Node *) malloc(sizeof(Node));

    NIL->value = NIL->height = 0;
    NIL->left = NIL->right = NULL;
}

void SVD(Node *node)
{
    if(node->left != NIL)
        SVD(node->left);

    fout<<node->value<<" ";

    if(node->right != NIL)
        SVD(node->right);
}

Node* rotright(Node *node)
{
    Node *t = node->left;

    node->left = t->right;
    t->right = node;

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

    return t;
}

Node* rotleft(Node *node)
{
    Node *t = node->right;

    node->right = t->left;
    t->left = node;

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

    return t;
}

Node* balance(Node *node)
{
    node->height = 1 + max(node->left->height, node->right->height);

    if(node->left->height > node->right->height + 1)
    {
        if(node->left->right->height > node->left->left->height)
            node->left = rotleft(node->left);

        node = rotright(node);
    }
    else
    if(node->right->height > node->left->height + 1)
    {
        if(node->right->left->height > node->right->right->height)
            node->right = rotright(node->right);

        node = rotleft(node);
    }

    return node;
}

Node* insert(Node *node, int value)
{
    if(node == NIL)
    {
        node = (Node *) malloc(sizeof(Node));

        node->value = value;
        node->height = 1;
        node->left = node->right = NIL;

        return node;
    }
    if(value < node->value)
        node->left = insert(node->left, value);
    else
        node->right = insert(node->right, value);

    return balance(node);
}

Node* erase(Node *node, int value)
{
    Node *t;

    if(node == NIL) return node;

    if(node->value == value)
    {
        if(node->left == NIL || node->right == NIL)
        {
            if(node->left == NIL) t = node->right;
                             else t = node->left;
            free(node);
            return t;
        }
        else
        {
            t = node->left;
            while(t->right != NIL) t = t->right;

            node->value = t->value;
            node->left = erase(node->left, t->value);

            return balance(node);
        }
    }

    if(value < node->value)
        node->left = erase(node->left, value);
    else
        node->right = erase(node->right, value);

    return balance(node);
}

int search(Node *node, int value)
{
    if(node == NIL) return 0;
    if(node->value == value) return 1;

    if(value < node->value)
        return search(node->left, value);
    else
        return search(node->right, value);
}

int main()
{
    init();

    fin>>n;

    for(int i=1;i<=n;i++)
    {
        tip = 1;

        if(tip != 4) fin>>value;

        if(tip == 1)
            Root = insert(Root,value); // insereaza valoare

        if(tip == 2)
            Root = erase(Root,value); // sterge valoare

        if(tip == 3)
        {
            if(search(Root,value))fout<<"Da"<<'\n'; // cauta vloare
                             else fout<<"Nu"<<'\n';
        }

        if(tip == 4)
        {
            SVD(Root);  // afiseaza valori sortate
            fout<<'\n';
        }
    }

    SVD(Root);

    return 0;
}