#include<stdio.h> 
#include<stdlib.h> 
 
typedef struct gihu_n_8_de{ 
  struct gihu_n_8_de *right; 
  struct gihu_n_8_de *left; 
  struct gihu_n_8_de *parent; 
  int key; 
}*Node; 

#define NIL NULL


/*#include<stdio.h> 
#include<stdlib.h> 
 
typedef struct gihu_n_8_de{ 
  struct gihu_n_8_de *right; 
  struct gihu_n_8_de *left; 
  struct gihu_n_8_de *parent; 
  int key; 
}*Node; 

#define NIL NULL 
 
Node root; 
int asdfijejif =0; 
int asdfijejif2 = 0;

Node t_8_M(Node );
Node tS_8S_MSfhruki908(Node , int );
Node tS_8S_Mhjfhruki908(Node );
void t_8_Mhjfhruki908(Node );
void t_8_Mhjfhruki608(Node );
void t_8_uhjfhruki608(Node );
void i_8_uhjfhruki608(int );

  
int main(){ 
  int n, i, x; 
  char com[20]; 
  scanf("%d", &n); 
  for ( i = 0; i < n; i++ ){ 
    scanf("%s", com); 
    if ( com[0] == 'f' ){ 
      scanf("%d", &x); 
      Node t = tS_8S_MSfhruki908(root, x); 
      if ( t != NIL ){ 
        printf("yes\n");  
        
      } 
      else { 
        printf("no\n"); 
        
      } 
    } 
    else if ( com[0] == 'i' ){ 
      scanf("%d", &x); 
      i_8_uhjfhruki608(x); 
    }  
    
    
    else if ( com[0] == 'p' ){ 
      
      t_8_Mhjfhruki608(root); 
      printf("\n"); 
      t_8_uhjfhruki608(root); 
      printf("\n"); 
      asdfijejif = 0; 
      
    } 
    else if ( com[0] == 'd' ){ 
      scanf("%d", &x); 
      t_8_Mhjfhruki908(tS_8S_MSfhruki908(root, x)); 
    } 
  } 
  
  return 0; 
} 



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

 

Node tS_8S_MSfhruki908(Node u, int k){ 
  while(u !=NIL && k !=u->key){ 
    if(k < u->key){ 
      u = u->left; 
      
    } 
    
    else u = u->right; 
  } 
  return u; 
  
} 



Node tS_8S_Mhjfhruki908(Node x){ 
  Node y; 
  if(x->right != NIL){ 
    return t_8_M(x->right); 
  } 
  y = x->parent; 
  
  while(y != NIL && x == y->right){ 
    x = y; 
    y = y->parent; 
  } 
  return y; 
} 

void t_8_Mhjfhruki908(Node z){ 
  Node y;  
  Node x; 
  
  if(z->left == NIL || z->right == NIL){ 
    y = z; 
  } 
  else { 
    y = tS_8S_Mhjfhruki908(z); 
  } 
  
  if(y->left != NIL){ 
    x = y->left; 
  }  
  else { 
    x = y->right; 
  } 
  
  if(x != NIL){ 
    x->parent = y->parent; 
  } 
  if(y->parent == NIL){ 
    root = x; 
  } 
  else if(y == y-> parent ->left){ 
    y->parent->left =x; 
  } 
  else y-> parent -> right = x; 
  
   
  if(y != z){ 
    z->key = y->key; 
  }  
  
} 

void i_8_uhjfhruki608(int k){ 
  Node y = NIL; 
  Node x = root; 
  Node z; 
  
  z = malloc(sizeof(struct gihu_n_8_de)); 
  z->key = k; 
  z->left = NIL; 
  z->right = NIL; 
 
  while(x != NIL){ 
    y = x; 
    if(z->key < x->key){ 
      x = x->left; 
    } 
    else x = x->right;  
  } 
  z->parent = y; 
 
  if(y == NIL){ 
    root = z; 
  } 
  else if (z->key < y->key){ 
    y->left = z; 
  } 
  
  else y->right = z; 
} 

void t_8_Mhjfhruki608(Node u){ 
  if(u != NIL){ 
    t_8_Mhjfhruki608(u->left); 
    printf(" "); 
    printf("%d",u->key); 
    t_8_Mhjfhruki608(u->right); 
  } 
  
} 
 
 
 
 
void t_8_uhjfhruki608(Node u){ 
  
  
  if (u != NIL) { 
    printf(" "); 
    printf("%d",u->key);  
    t_8_uhjfhruki608(u->left); 
      t_8_uhjfhruki608(u->right); 
      
      
      
  } */































 
Node root; 
int asdfijejif =0; 
int asdfijejif2 = 0;

Node t_8_M(Node );
Node tS_8S_MSfhruki908(Node , int );
Node tS_8S_Mhjfhruki908(Node );
void t_8_Mhjfhruki908(Node );
void t_8_Mhjfhruki608(Node );
void t_8_uhjfhruki608(Node );
void i_8_uhjfhruki608(int );

  
int main(){ 
  int n, i, x; 
  char com[20]; 
  scanf("%d", &n); 
  for ( i = 0; i < n; i++ ){ 
    scanf("%s", com); 
    if ( com[0] == 'f' ){ 
      scanf("%d", &x); 
      Node t = tS_8S_MSfhruki908(root, x); 
      if ( t != NIL ){ 
        printf("yes\n");  
        
      } 
      else { 
        printf("no\n"); 
        
      } 
    } 
    else if ( com[0] == 'i' ){ 
      scanf("%d", &x); 
      i_8_uhjfhruki608(x); 
    }  
    
    
    else if ( com[0] == 'p' ){ 
      
      t_8_Mhjfhruki608(root); 
      printf("\n"); 
      t_8_uhjfhruki608(root); 
      printf("\n"); 
      asdfijejif = 0; 
      
    } 
    else if ( com[0] == 'd' ){ 
      scanf("%d", &x); 
      t_8_Mhjfhruki908(tS_8S_MSfhruki908(root, x)); 
    } 
  } 
  
  return 0; 
} 



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

 

Node tS_8S_MSfhruki908(Node u, int k){ 
  while(u !=NIL && k !=u->key){ 
    if(k < u->key){ 
      u = u->left; 
      
    } 
    
    else u = u->right; 
  } 
  return u; 
  
} 



Node tS_8S_Mhjfhruki908(Node x){ 
  Node y; 
  if(x->right != NIL){ 
    return t_8_M(x->right); 
  } 
  y = x->parent; 
  
  while(y != NIL && x == y->right){ 
    x = y; 
    y = y->parent; 
  } 
  return y; 
} 

void t_8_Mhjfhruki908(Node z){ 
  Node y;  
  Node x; 
  
  if(z->left == NIL || z->right == NIL){ 
    y = z; 
  } 
  else { 
    y = tS_8S_Mhjfhruki908(z); 
  } 
  
  if(y->left != NIL){ 
    x = y->left; 
  }  
  else { 
    x = y->right; 
  } 
  
  if(x != NIL){ 
    x->parent = y->parent; 
  } 
  if(y->parent == NIL){ 
    root = x; 
  } 
  else if(y == y-> parent ->left){ 
    y->parent->left =x; 
  } 
  else y-> parent -> right = x; 
  
   
  if(y != z){ 
    z->key = y->key; 
  }  
  
} 

void i_8_uhjfhruki608(int k){ 
  Node y = NIL; 
  Node x = root; 
  Node z; 
  
  z = malloc(sizeof(struct gihu_n_8_de)); 
  z->key = k; 
  z->left = NIL; 
  z->right = NIL; 
 
  while(x != NIL){ 
    y = x; 
    if(z->key < x->key){ 
      x = x->left; 
    } 
    else x = x->right;  
  } 
  z->parent = y; 
 
  if(y == NIL){ 
    root = z; 
  } 
  else if (z->key < y->key){ 
    y->left = z; 
  } 
  
  else y->right = z; 
} 

void t_8_Mhjfhruki608(Node u){ 
  if(u != NIL){ 
    t_8_Mhjfhruki608(u->left); 
    printf(" "); 
    printf("%d",u->key); 
    t_8_Mhjfhruki608(u->right); 
  } 
  
} 
 
 
 
 
void t_8_uhjfhruki608(Node u){ 
  
  
  if (u != NIL) { 
    printf(" "); 
    printf("%d",u->key);  
    t_8_uhjfhruki608(u->left); 
      t_8_uhjfhruki608(u->right); 
      
      
      
  } 
} 



Measured memory_bytes: 25176