#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;


struct Node {
    int v;
    Node* p;
    Node* l;
    Node* r;
};

Node* root = NULL;

Node* find(int v) {
    Node* x = root;
    while (x && x->v != v) {
        if (v < x->v) {
            x = x -> l;
        } else if (v > x-> v) {
            x = x -> r;
        }
    }
    return x;
}

Node* findMin(Node* x) {
    while (x -> l) x = x -> l;
    return x;
}

Node* successor(Node* x) {
    if (x -> r != NULL) return findMin(x->r);
    Node* y = x -> p;
    while (y && x == y -> r) {
        x = y;
        y = y -> r;
    }
    return y;
}

void del(int v) {
    Node* p = find(v);
    Node* le = p -> l;
    Node* ri = p -> r;
    if (!le || !ri) {
        Node* parent = p -> p;
        if (parent) {
            Node* x = NULL;
            if (le) x = le;
            if (ri) x = ri;
            if (parent->l == p) parent->l = x;
            if (parent->r == p) parent->r = x;
            if (x) x->p = parent;
            delete p;
            return ;
        } else {
            Node* x = NULL;
            if (le) x = le;
            if (ri) x = ri;
            if (x) x->p = NULL;
            delete p;
            root = x;
            return ;
        }
    } else {
        Node* succ = successor(p);
        swap(succ->v, p->v);
        Node* parent = succ -> p;
        if (parent) {
            if (parent->l == succ) parent->l = succ->r;
            if (parent->r == succ) parent->r = succ->r;
            if (succ->r) succ->r->p = parent;
            delete succ;
            return ;
        } else {
            if (succ->r) succ->r->p = NULL;
            root = succ->r;
            delete succ;
            return ;
        }
    }
}

void insert(int v) {
    if (!root) {
        root = new Node;
        root -> v = v;
        root -> l = NULL;
        root -> r = NULL;
        root -> p = NULL;
        return;
    }

    Node* par = NULL;
    Node* x = root;
    while (x) {
        par = x;
        if (v < x -> v) {
            x = x -> l;
        } else {
            x = x -> r;
        }
    }
    if (v < par->v) {
        par -> l = new Node;
        Node* p = par -> l;
        p -> v = v;
        p -> l = NULL;
        p -> r = NULL;
        p -> p = par;
    } else {
        par -> r = new Node;
        Node* p = par -> r;
        p -> v = v;
        p -> l = NULL;
        p -> r = NULL;
        p -> p = par;
    }
}

void preOrder(Node* root) {
    if (root == NULL) return ;
    printf(" %d", root -> v);
    preOrder(root -> l);
    preOrder(root -> r);
}

void inOrder(Node* root) {
    if (root == NULL) return ;
    inOrder(root -> l);
    printf(" %d", root -> v);
    inOrder(root -> r);
}


int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n;
    int num;
    char s[10];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        if (s[0] == 'i') {
            scanf("%d", &num);
            insert(num);
        } else if (s[0] == 'p') {
            inOrder(root);
            printf("\n");
            preOrder(root);
            printf("\n");
        } else if (s[0] == 'f') {
            scanf("%d", &num);
            if (find(num)) printf("yes\n");
            else printf("no\n");
        } else if (s[0] == 'd') {
            scanf("%d", &num);
            del(num);
        }
    }
    return 0;
}

Measured memory_bytes: 21932