#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<stdlib.h>
#include<math.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007
typedef struct node * nodept;

struct node{
    int key = -1;
    node *par;
    node *right;
    node *left;
};

nodept nil, root;

void init(){
    nil = (nodept)malloc(sizeof(node));
    nil->par = nil;
    nil->left = nil;
    nil->right = nil;

    root = nil;
}

void insert(int key){
    nodept z;
    z = (nodept)malloc(sizeof(node));
    z->key = key;
    z->par = nil;
    z->right = nil;
    z->left = nil;
    
    nodept y = nil;
    nodept x = root;

    while(x != nil){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }
        else {
            x = x->right;
        }
    }

    z->par = y;

    if(y == nil){
        root = z;
    }
    else if(z->key < y->key){
        y->left = z;
    }
    else {
        y->right = z;
    }
}

nodept find(int key){
    nodept x = root;
    while(x != nil){
        if(x->key == key){
            break;
        }
        else if(key < x->key){
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
    return x;
}

void deletenode1(nodept x){
    if(x->left != nil){
        x->left->par = x->par;
        if(x == x->par->left){
            x->par->left = x->left;
        }
        else {
            x->par->right = x->left;
        }
    }
    else if(x->right != nil){
        x->right->par = x->par;
        if(x == x->par->left){
            x->par->left = x->right;
        }
        else {
            x->par->right = x->right;
        }
    }
    else {
        if(x == x->par->left){
            x->par->left = nil;
        }
        else {
            x->par->right = nil;
        }
    }
    x->par = nil;
    x->left = nil;
    x->right = nil;
}

void deletenode2(nodept x){
    nodept y = nil;
    nodept z = x->right;
    while(z != nil){
        //node change!
        y = z;
        z = z->left;
    }
    if(y != x->right)y->par->left = nil;
    y->par = x->par;
    if(x == x->par->left){
        x->par->left = y;
    }
    else {
        x->par->right = y;
    }
    y->left = x->left;
    if(x->right != y)y->right = x->right;
    if(y->left != nil)y->left->par = y;
    if(y->right != nil)y->right->par = y;
    x->par = nil;
    x->left = nil;
    x->right = nil;
}

void Delete(int key){
    nodept x = find(key);
    if(x == nil)return;
    if(x->left == nil || x->right == nil){
        deletenode1(x);
        return;
    }
    deletenode2(x);
}

void indfs(nodept v){
    if(v == nil)return;
    if(v->left != nil){
        indfs(v->left);
    }
    printf(" %d", v->key);
    if(v->right != nil){
        indfs(v->right);
    }
}

void predfs(nodept v){
    if(v == nil)return;
    printf(" %d", v->key);
    if(v->left != nil){
        predfs(v->left);
    }
    if(v->right != nil){
        predfs(v->right);
    }
}

signed main(){
    int M;
    cin >> M;
    init();
    for(int i = 0; i < M; i++){
        char query[10];
        cin >> query;
        if(query[0] == 'i'){
            int key;
            cin >> key;
            insert(key);
        }
        else if(query[0] == 'f'){
            int key;
            cin >> key;
            if(find(key) != nil){
                printf("yes\n");
            }
            else printf("no\n");
        }
        else if(query[0] == 'd'){
            int key;
            cin >> key;
            Delete(key);
        }
        else {
            indfs(root);
            printf("\n");
            predfs(root);
            printf("\n");
        }
    }


    return 0;
}


Measured memory_bytes: 21832