#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};
/*
 * 
 */
//NIL mean null
Node *root, *NIL;


void insert(int key) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z -> key = key;
    z -> left = NIL;
    z -> right = NIL;
    
    while(x != NIL) {
        y = x;
        if(x -> key < key) {
            //??????
            x = x -> right;
        }
        else {
            //??????
            x =  x -> left;
        }
    }
    
    z -> parent = y;
    if(y == NIL) {
        root = z;
    }
    else if(y -> key < key) {
        y -> right = z;
    }
    else {
        y -> left = z;
    }
}


Node* find(int key) {
    Node *node = root;
    while(node != NIL) {
        if(node -> key == key) {
            //cout << "yes" << endl;
            return node;
        }
        else if(node -> key < key) {
            //??????
            node = node -> right;
        }
        else if(node -> key > key){
            //??????
            node = node -> left;
        }

    }
    //cout << "no" << endl;
    return NIL;
}

void printInOrder(Node *node) {
    if(node == NIL) {
        return;
    }
    printInOrder(node -> left);
    cout << " " << node -> key;
    printInOrder(node -> right);
}

void printPreOrder(Node *node) {
    if(node == NIL) {
        return;
    }
    cout << " " << node -> key;
    printPreOrder(node -> left);
    printPreOrder(node -> right);
}

void releaseTree(Node *node) {
    if(node == NIL) {
        return;
    }
    releaseTree(node -> left);
    releaseTree(node -> right);
    free(node);
}
Node* treeMinimum(Node *x) {
    while(x -> left != NIL) {
        x = x -> left;
    }
    return x;
}

Node* treeSuccessor(Node *node) {
    if(node -> right != NIL) {
        return treeMinimum(node -> right);
    }
    Node *y = node -> parent;
    while(y != NIL && node == y -> right) {
        node = y;
        y = y -> parent;
    }
    return y;
}

void deleteNode(Node *z) {
    Node *y;
    Node *x;
    
    if(z -> left == NIL || z -> right == NIL) {
        y = z;
    }
    else {
        y = treeSuccessor(z);
    }
    
    if(y -> left != NIL) {
        x = y -> left;
    }
    else {
        x = y -> right;
    }
    
    if(x != NIL) {
        x -> parent = y -> parent;
    }
    
    if(y -> parent == NIL) {
        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(void) {
    //ifstream ifs;
    //ifs.open("./input.txt", ifstream::in);
    
    int num, key;
    string command;
    cin >> num;
    
    for(int i = 0; i < num; i++) {
        cin >> command;
        if(command[0] == 'i') {
            cin >> key;
            insert(key);
        }
        else if(command[0] == 'p') {
            printInOrder(root);
            cout << endl;
            printPreOrder(root);
            cout << endl;
        }
        else if(command[0] == 'f') {
            cin >> key;
            Node *node;
            node = find(key);
            if(node == NIL) {
                cout << "no" << endl;
            }
            else {
                cout <<"yes" << endl;
            }
        }
        else if(command[0] == 'd') {
            cin >> key;
            deleteNode(find(key));
        }
    }
    
    releaseTree(root);
   
    return 0;
}

Measured memory_bytes: 19956