#include<stdio.h>
#define NIL -1
#define MAX 500000
int root = NIL;
int key[MAX];
int left[MAX];
int right[MAX];
//int T[MAX];
int p[MAX];
void tree_insert(int z){
  int y = NIL;
  int x = root;
  while(x!=NIL){
    y = x;
    if(key[z] < key[x])x = left[x];
    else x = right[x];
  }
  p[z] = y;
  if(y == NIL)root = z;
  else if(key[z]<key[y])left[y] = z;
  else right[y] = z;
  
}
void preorder(int t){
  if(t==NIL)return;
  printf(" %d",key[t]);
  preorder(left[t]);
  preorder(right[t]);
}

void inorder(int t){
  if(t==NIL)return;
  inorder(left[t]);
  printf(" %d",key[t]);
  inorder(right[t]);
}

void print(){
  inorder(root);
  printf("\n");
  preorder(root);
  printf("\n");
}

int tree_find(int t){
  int i=0;
  int y=NIL;
  int x=root;
  while(x!=NIL){
    if(key[x]==t)return x;
    y = x;
    if(t < key[x])x = left[x];
    else x = right[x];
  }
  return NIL;
}
///////////////////////////////////////////////////////
void delete(int z){
  int x,y;
  if(left[z]==NIL||right[z]==NIL)y=z;
  else y = tree_successor(z);
  
  if(left[y]!=NIL)x=left[y];
  else x=right[y];
  
  if(x!=NIL)p[x]=p[y];
  
  if(p[y]==NIL)root=x;
  else if(y==left[p[y]])left[p[y]]=x;
  else right[p[y]]=x;

  if(y!=z)key[z]=key[y];

}
////////////////////////////////////////////////////////
int tree_successor(int x){
  int y=NIL;
  if(right[x] != NIL)return tree_minimum(right[x]);
  y = p[x];
  while(y != NIL && x == right[y]){
    x = y;
    y = p[y];
  }
  return y;
}
int tree_minimum(int x){
  while(left[x] != NIL){
    x = left[x];
  }
  return x;
}

int main(){
  
  int i,n,x;
  int z = 0;
  char A[10];
  scanf("%d",&n);
  for(i=0;i<MAX;i++){
    key[i]=NIL;
    left[i]=NIL;
    right[i]=NIL;
    //   T[MAX]=NIL;
    p[i]=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%s", A);
    if(A[0]=='i'){
      scanf("%d",&x);
      key[z]=x;
      tree_insert(z);
      z++;
    }
    else if(A[0]=='p')print();
    else if(A[0]=='f'){
       scanf("%d",&x);
       if(tree_find(x)!=NIL)printf("yes\n");
       else printf("no\n");
    }
    else if(A[0]=='d'){
      scanf("%d",&x);
      x=tree_find(x);
      delete(x);
    }
  }
  
  return 0;
}