#include <stdio.h>
#include <malloc.h>


struct Node
{
    int key;
    Node *parent,*right,*left;
};
Node *root = NULL;
void inserts(int key)
{
    Node *z,*y,*x;
    z = (Node*)malloc(sizeof(Node));
    z->key = key;
    z->left = z->parent = z->right = NULL;
    y = NULL;
    x = root;
    while(x!=NULL)
    {
        y = x;
        if(x->key < z->key)
            x = x->right;
        else
            x = x->left;
    }
    z->parent = y;
    if(y==NULL)
    {
        root = z;
    }
    else if(z->key < y->key)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }
}
void preParse(Node *x)
{
    if(x==NULL)
    {
        return ;
    }
    printf(" %d",x->key);
    preParse(x->left);
    preParse(x->right);
}
void inParse(Node *x)
{
    if(x==NULL)
    {
        return;
    }
    inParse(x->left);
    printf(" %d",x->key);
    inParse(x->right);
}
void print()
{
    inParse(root);
    putchar('\n');
    preParse(root);
    putchar('\n');
}
int finda(int key)
{
    Node *x,*y = root;
    x = (Node*)malloc(sizeof(Node));
    x->key = key;
    x->left = x->parent = x->right = NULL;
    while(y!=NULL)
    {
        if(x->key<y->key)
            y = y->left;
        else if(x->key>y->key)
            y = y->right;
        else if(x->key==y->key)
            return 1;
    }
    return 0;
}
Node *findade(int key)
{
    Node *x,*y = root;
    x = (Node*)malloc(sizeof(Node));
    x->key = key;
    x->left = x->parent = x->right = NULL;
    while(y!=NULL)
    {
        if(x->key<y->key)
            y = y->left;
        else if(x->key>y->key)
            y = y->right;
        else if(x->key==y->key)
            return y;
    }
}

Node* getMinimum(Node *x)
{
    while(x->left!=NULL)
        x = x->left;
    return x;
}
Node* GetSuccesser(Node *z)
{
    if(z->right!=NULL){
        return getMinimum(z->right);
    }
    Node *y;
    y = z->parent;
    while (y!=NULL&&z==y->right)
    {
        z = y;
        y = y->parent;
    }
    return y;
}

void deletea(Node *z)
{
    Node *y,*x;

    if(z->left==NULL||z->right==NULL){
        y = z;
    }
    else y = GetSuccesser(z);
    if(y->left!=NULL){
        x = y->left;
    }
    else x = y->right;
    if(x!=NULL){
        x->parent = y->parent;
    }
    if(y->parent==NULL){
        root = x;
    }
    else if(y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
    if(y!=z){
        z->key = y->key;
    }
    free(y);
}
int main()
{
    int m,key,i;
    char com[7];
    scanf("%d",&m);
    for(i = 0; i < m; i++)
    {
        scanf("%s",&com);
        if(com[0]=='i')
        {
            scanf("%d",&key);
            inserts(key);
        }
        else if(com[0]=='p')
        {
            print();
        }
        else if(com[0]=='f')
        {
            scanf("%d",&key);
            if(finda(key))printf("yes\n");
            else printf("no\n");
        }
        else if(com[0]=='d'){
                scanf("%d",&key);
                deletea(findade(key));
        }
    }
    return 0;
}
//void deletea(Node *y)
//{
//    Node *x = NULL;
//    x = (Node*)malloc(sizeof(Node));
//    if(y->left==NULL&&y->right==NULL)
//    {
//        x = y;
//        y = y->parent;
//        if(y->left==x)
//            y->left = NULL;
//        else y->right = NULL;
//        free(x);
//    }
//    else if(y->left==NULL&&y->right!=NULL){
//        x = y;
//        y = y->parent;
//        if(y->left->key==x->key){
//            y->left = x->right;
//            x->right->parent = y;
//        }
//        else
//        {
//            y->right = x->right;
//            x->right->parent = y;
//        }
//        free(x);
//    }
//    else if(y->left!=NULL&&y->right==NULL){
//        x = y;
//        y = y->parent;
//        if(y->left->key==x->key){
//            y->left = x->left;
//            x->left->parent = y;
//        }
//        else
//        {
//            y->right = x->left;
//            x->left->parent = y;
//        }
//        free(x);
//    }
//    else
//    {
//        x = y;
//        y = y->parent;
//        Node *z,*q;
//        if(y->left->key==x->key)
//        {
//
//            z = x->left,q = x->right;
//            while(z->right!=NULL)z = z->right;
//            z->right = q->left;
//            q->left->parent = z;
//            q->left = NULL;
//            x->left->parent = q;
//            q->left = x->left;
//            y->left = q;
//            q->parent = y;
//        }
//        else
//        {
//            z = x->left,q = x->right;
//            while(z->right!=NULL)z = z->right;
//            z->right = q->left;
//            q->left->parent = z;
//            q->left = NULL;
//            x->left->parent = q;
//            q->left = x->left;
//            y->right = q;
//            q->parent = y;
//        }
//        free(x);
//    }
//    while(y->parent!=NULL)
//     root = y;
//}



Measured memory_bytes: 21364