#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *left,*right;
}*root=NULL;
void insert(int x) {
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    p->data=x;
    p->right=NULL;
    p->left=NULL;
    if(root==NULL) root=p;
    else {
        struct node *tmp=root,*prev;
        while(tmp!=NULL) {
            prev = tmp;
            if(x > tmp->data) {
                tmp = tmp->right;
            }
            else {
                tmp = tmp->left;
            }
        }
        if(x < prev->data) prev->left=p;
        else prev->right=p;
    }
}
void preorder(struct node* tmp) {
    if(tmp==NULL) return;
    printf("%d ",tmp->data);
    preorder(tmp->left);
    preorder(tmp->right);
}
void inorder(struct node* tmp) {
    if(tmp==NULL) return;
    inorder(tmp->left);
    printf("%d ",tmp->data);
    inorder(tmp->right);
}
void postorder(struct node* tmp) {
    if(tmp==NULL) return;
    postorder(tmp->left);
    postorder(tmp->right);
    printf("%d ",tmp->data);
}
void delete(int x) {
    struct node *prev,*tmp = root;
    while(tmp->data!=x) {
        if(x < tmp->data) {
            prev = tmp;
            tmp=tmp->left;
        }
        else if(x > tmp->data) {
            prev = tmp;
            tmp=tmp->right;
        }
    }
    if(tmp->right==NULL && tmp->left==NULL) {
        if(prev->right == tmp) prev->right=NULL;
        else prev->left = NULL;
        free(tmp);
    }
    else if((tmp->right==NULL && tmp->left!=NULL)) {
        if(prev->left==tmp) prev->left = tmp->left;
        else prev->right = tmp->left;
        free(tmp);
    }
    else if((tmp->right!=NULL && tmp->left==NULL)) {
        if(prev->left==tmp) prev->left = tmp->right;
        else prev->right = tmp->right;
        free(tmp);
    }
    else if(tmp->left!=NULL && tmp->right!=NULL) {
        struct node *newprev,*curr = tmp->right;
        newprev = tmp;
        while(curr->left!=NULL) {
            newprev = curr;
            curr=curr->left;
        }
        tmp->data = curr->data;
        if(newprev==tmp) newprev->right=NULL;
        else
        newprev->left = NULL;
        free(curr);
    }
}
int main () {
    int c,n,x;
    while(1) {
        scanf("%d",&c);
        switch(c) {
            case 1: scanf("%d",&n);
                    for(int i=0;i<n;i++) {
                        scanf("%d",&x);
                        insert(x);
                    }
                    printf("BST with %d nodes is ready to use!\n",n);
            break;

            case 2: printf("BST Traversal in INORDER\n");
                    inorder(root);
                    printf("\n");
            break;

            case 3: printf("BST Traversal in PREORDER\n");
                    preorder(root);
                    printf("\n");
            break;

            case 4: printf("BST Traversal in POSTORDER\n");
                    postorder(root);
                    printf("\n");
            break;

            case 5: scanf("%d",&x); delete(x); break;

            case 6: exit(0);

        }
    }
}