#include<bits/stdc++.h>
using namespace std;
struct node{
  node* l;
  node* r;
  node* p;
  int key;
};

node L;
node* nil=&L;
node* t=nil;

node* find(node* a,int t){
  if(a->key==t)return a;
  if(a==nil)return nil;
  if(a->key<t)return find(a->r,t);
  return find(a->l,t);
}

void insert(node* a){
  node* y=nil;
  node* x=t;
  while(x!=nil){
    y=x;
    if(a->key<x->key)x=x->l;
    else x=x->r;
  }
  a->p=y;
  if(y==nil)t=a;
  else if(a->key<(y->key))y->l=a;
  else y->r=a;
}

node* treeMinimum(node* a){
  while(a->l!=nil)
    a=a->l;
  return a;
}

node* treeSuccessor(node* a){
  if(a->r!=nil)
    return treeMinimum(a->r);
  node* b=a->p;
  while(b!=nil&&a==b->r){
    a=b;
    b=b->p;
  }
}

void del(node* z){
  node* x,*y;
  if(z->l==nil||z->r==nil)y=z;
  else y=treeSuccessor(z);
  if(y->l!=nil)x=y->l;
  else x=y->r;
  if(x!=nil)x->p=y->p;
  if(y->p==nil)t=x;
  else if(y==y->p->l)y->p->l=x;
  else y->p->r=x;
  if(y!=z)z->key=y->key;
}

void pri(node* b,int a){
  if(b==nil)return;
  if(!a)cout<<" "<<b->key;
  pri(b->l,a);
  if(a)cout<<" "<<b->key;
  pri(b->r,a);
}

int main(){
  int n,a;
  string s;
  cin>>n;
  
  for(int i=0;i<n;i++){
    cin>>s;
    if(s[0]=='i'){
      cin>>a;
      node* b=(node *)malloc(sizeof(node));
      b->l=nil;
      b->r=nil;
      b->key=a;
      insert(b);
    }
    else if(s[0]=='f'){
      cin>>a;
      if(find(t,a)!=nil)cout<<"yes"<<endl;
      else cout<<"no"<<endl;
    }
    else if(s[0]=='d'){
      cin>>a;
      del(find(t,a));
    }
    else{
      pri(t,1);
      cout<<endl;
      pri(t,0);  
      cout<<endl;
    }
  }
  return 0;
}