#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *l;
  struct node *r;
  struct node *p;
  int key;
};

typedef struct node*Node;

Node root;

Node TreeMim(Node x){

  while(x->l!=NULL){
    x=x->l;
  }
  return x;
}

Node TreeSearch(Node x,int k){
  if(x==NULL||k==x->key){
    return x;
  }
  if(k<x->key){
    return TreeSearch(x->l,k);
  }else{
    return TreeSearch(x->r,k);
  }
}

Node TreeSuccessor(Node x){
  Node y,p;
  if(x->r!=NULL){
    return TreeMim(x->r);
  }
  y=x->p;
  while(y!=NULL&&x==y->r){
    x=y;
    y=y->p;
  }
  return y;
}

void TreeDelete(Node z){

  Node x,y;

  if(z->l==NULL||z->r==NULL){
    y=z;
  }else{
    y=TreeSuccessor(z);
  }
  if(y->l!=NULL){
    x=y->l;
  }else{
    x=y->r;
  }
  if(x!=NULL){
    x->p=y->p;
  }
  if(y->p==NULL){
    root=x;
  }else if(y==y->p->l){
    y->p->l=x;
  }else{
    y->p->r=x;
  }

  if(y!=z){
    z->key=y->key;
  }
}
void TreeInsert(int k){
  Node y=NULL;
  Node x=root;
  Node z;

  z=malloc(sizeof(struct node));

  z->key=k;
  z->l=NULL;
  z->r=NULL;

  while(x!=NULL){
    y=x;
    if(z->key<x->key){
      x=x-1;
    }else{
      x=x->r;
    }
  }
  z->p=y;

  if(y==NULL){
    root=z;
  }else if(z->key<y->key){
    y->l=z;
  }else{
    y->r=z;
  }
}

void Inorder(Node u){

  if(u!=NULL){
    Inorder(u->l);
    printf(" %d",u->key);
    Inorder(u->r);
  }
}

void Preorder(Node u){
  printf(" %d",u->key);
  if(u!=NULL){
    if(u->l!=NULL)
      Preorder(u->l);
   
    if(u->r!=NULL)
      Preorder(u->r);
  }
}

int main(){

  int n,x,i;
  char A[20];

  scanf("%d",&n);

  for(i=0;i<n;i++){

    scanf("%s",A);

    if(A[0]=='f'){
      scanf("%d",&x);
      Node t=TreeSearch(root,x);
      if(t!=NULL){
	printf("yes\n");
      }else{
	printf("no\n");
      }
    }else if(A[0]=='i'){
      scanf("%d",&x);
      TreeInsert(x);
    }else if(A[0]=='p'){
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }else if(A[0]=='d'){
      scanf("%d",&x);
      TreeDelete(TreeSearch(root,x));
    }
  }
  return 0;
}