
#include<stdio.h>
#include<stdlib.h>

#define NIL NULL

typedef struct node{
    int key;
    struct node *l;
    struct node *r;
    struct node *p;
} Node;

typedef struct node* NodePointer;

NodePointer root;

void Delete(NodePointer t){
    
    NodePointer x, y;
    
    if(t->l != NIL || y->r == NIL) y = t;
    else y = Successor(t);
    
    if(y->l != NIL) x = y->l;
    else x = y->r;
    
    if(x != NIL) x->p = y->p;
    
    if(y->p == NIL) root = x;
    else {
        if(y == y->p->l) y->p->l = x;
        else y->p->r = x;
        
        if(y != t) t->key = y->key;
        
        y = t;
        
    }
}

NodePointer Minimum(NodePointer t){
    
    while(t->l != NIL) t = t->l;
    
    return t;
    
}

NodePointer Search(NodePointer t, int key){
    
    if(t == NIL || key == t->key) return t;
    if(key < t->key) return Search(t->l, key);
    else return Search(t->r, key);
    
}

NodePointer Successor(NodePointer t){
    
    NodePointer y;
    
    if(t->r != NIL) return Minimum(t->r);
    
    y = t->p;
    
    while(y != NIL && t == y->r){
        t = y;
        y = y->p;
    }
    
    return y;
    
}

void Find(NodePointer t, int key){
    
    while(t != NIL){
        if(key == t->key){
            printf("yes\n");
            break;
        }
        else if(key < t->key) t = t->l;
        else t = t->r;
    }
    
    if(t == NIL) printf("no\n");
    
}

void Inorder(NodePointer t){
    
    if(t->l != NIL) Inorder(t->l);
    printf(" %d", t->key);
    if(t->r != NIL) Inorder(t->r);
    
}

void Preorder(NodePointer t){
    
    printf(" %d", t->key);
    if(t->l != NIL) Preorder(t->l);
    if(t->r != NIL) Preorder(t->r);
    
}

void Insert(int key){
    
    NodePointer x, y, z;
    
    y = NIL;
    x = root;
    
    z = malloc(sizeof(struct node));
    z->key = key;
    z->l = NIL;
    z->r = NIL;
    
    while(x != NIL){
        y = x;
        if(z->key < x->key) x = x->l;
        else x = x->r;
        z->p = y;
    }
    
    z->p = y;
    
    if(y == NIL) root = z;
    else if(z->key < y->key) y->l = z;
    else y->r = z;
    
}

int main(){
    
    int i, n, x, key1, key2;
    char com[10];
    
    scanf("%d",&n);
    
    for ( i = 0; i < n; i++ ){
        scanf("%s", com);
        if(com[0] == 'i'){
            scanf("%d", &x);
            Insert(x);
        }
        else if(com[0] == 'p'){
            Inorder(root);
            printf("\n");
            Preorder(root);
            printf("\n");
        }
        else if(com[0] == 'f'){
            scanf("%d", &key1);
            Find(root, key1);
        }
        else if (com[0] == 'd'){
            scanf("%d", &key2);
            Delete(Search(root, key2));
            printf("\n");
        }
    }
    
    return 0;
    
}