#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

/*********** Constants ***********/
const auto INF = static_cast<ll>(1ll << 60);
const auto MOD = static_cast<ll>(1e9 + 7);
const auto NIL = nullptr;

/************* Utils *************/
struct Node {
    ll key;
    Node *parent, *left, *right;
};

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

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

void insert(Node **T, Node **z) {
    Node *y = NIL;
    Node *x = *T;
    while (x != NIL) {
        y = x;
        if ((*z)->key < x->key) {
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
    (*z)->parent = y;
    if (y == NIL) {
        *T = *z;
    }
    else if ((*z)->key < y->key) {
        y->left = *z;
    }
    else {
        y->right = *z;
    }
}

Node *find(Node **T, ll key) {
    Node *x = *T;
    while (x != NIL) {
        if (x->key == key) {
            return x;
        }
        else if (x->key > key) {
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
    return NIL;
}

Node *getMinimum(Node *x) {
    while (x->left != NIL) {
        x = x->left;
    }
    return x;
}

Node *getSuccesser(Node **T, Node *x) {
    if (x->right != NIL) {
        return getMinimum(x->right);
    }
    Node *y = x->parent;
    while (y != NIL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

void deleteNode(Node **T, Node *z) {
    Node *x, *y;
    if (z->left == NIL || z->right == NIL) {
        y = z;
    }
    else {
        y = getSuccesser(T, z);
    }

    if (y->left != NIL) {
        x = y->left;
    }
    else {
        x = y->right;
    }

    if (x != NIL) {
        x->parent = y->parent;
    }

    if (y->parent == NIL) {
        *T = 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);
}

void del(Node **T, ll key) {
    Node *x;
    while ((x = find(T, key)) != NIL) {
        deleteNode(T, x);
    }
}

/*********** Variables ***********/
Node *Tree;

/*********** Functions ***********/
bool init() {
    return true;
}

void solve() {
    ll N; cin >> N;
    string command;
    for (ll i = 0; i < N; i++) {
        cin >> command;
        if (command == "print") {
            inOrder(&Tree);
            cout << endl;
            preOrder(&Tree);
            cout << endl;
        }
        else if (command == "find") {
            ll key; cin >> key;
            if (find(&Tree, key) != NIL) {
                cout << "yes" << endl;
            }
            else {
                cout << "no" << endl;
            }
        }
        else if (command == "delete") {
            ll key; cin >> key;
            del(&Tree, key);
        }
        else {
            ll key; cin >> key;
            Node *node = new Node{key, NIL, NIL, NIL};
            insert(&Tree, &node);
        }
    }
}

void output() {
}

int main() {
    //init();
    solve();
    //output();
    return 0;
}


Measured memory_bytes: 21804