import java.util.*;

class BinaryTree<T extends Comparable<? super T>> {
    
    class Node<T>{
        
        Node<T> left;
        Node<T> right;
        T key;
        
        Node(T newKey) {
            left = null;
            right = null;
            key = newKey;
        }
    }
    
    private Node<T> root;
    public BinaryTree() {
        root = null;
    }
    
    public void insert(T newKey) {
        Node<T> workNode = root;
        Node<T> parentNode = null;
        while (workNode != null) {
            parentNode = workNode;
            if (newKey.compareTo(workNode.key) < 0) {
                workNode = workNode.left;
            } else {
                workNode = workNode.right;
            }
        }
        if (parentNode == null) {
            root = new Node<T>(newKey);
        } else if (newKey.compareTo(parentNode.key) < 0) {
            parentNode.left = new Node<T>(newKey);
        } else {
            parentNode.right = new Node<T>(newKey);
        }
    }
    
    public T delete(T key) {
        if (root == null) {
            return null;
        }
        
        Node<T> workNode = root;
        Node<T> parentNode = null;
        while (key.compareTo(workNode.key) != 0) {
            if (key.compareTo(workNode.key) < 0) {
                if (workNode.left == null) {
                    return null;
                }
                parentNode = workNode;
                workNode = workNode.left;
            } else {
                if (workNode.right == null) {
                    return null;
                }
                parentNode = workNode;
                workNode = workNode.right;
            }
        }
        
        if (workNode.right == null) {
            setChild(parentNode, workNode.left, workNode.key);
            return workNode.key;
        } else if (workNode.left == null) {
            setChild(parentNode, workNode.right, workNode.key);
            return workNode.key;
            
        } else {
            Node<T> replaceNode = workNode.left;
            Node<T> parentReplaceNode = workNode;
            
            while (replaceNode.right != null) {
                parentReplaceNode = replaceNode;
                replaceNode = replaceNode.right;
            }
            
            if (parentReplaceNode == workNode) {
                setChild(parentNode, replaceNode, workNode.key);
                parentReplaceNode.left = null;
                replaceNode.right = workNode.right;
            } else {
                setChild(parentNode, replaceNode, workNode.key);
                parentReplaceNode.right = replaceNode.left;
                replaceNode.left = workNode.left;
                replaceNode.right = workNode.right;
            }
            return workNode.key;
        }
    }
    
    private Node<T> setChild
	(Node<T> targetNode, Node<T> newNode, T key) {
        if (targetNode == null) {
            root = newNode;
            return null;
        } else if (key.compareTo(targetNode.key) < 0) {
            targetNode.left = newNode;
            return targetNode;
        } else {
            targetNode.right = newNode;
            return targetNode;
        }
    }
    
    public T printAll() {
        if (root == null) {
            System.out.println("null");
            return null;
        } else {
            traverseInorder(root);
            System.out.println();
            return root.key;
        }
    }
    
    private void traverseInorder(Node<T> tempNode) {
        if (tempNode != null) {
            traverseInorder(tempNode.left);
            System.out.print("(" + tempNode.key + ") ");
            traverseInorder(tempNode.right);
        } else {
            return;
        }
    }
    
    public static void main(String[] args) {
        BinaryTree<Integer> tree = new BinaryTree<>();
        Scanner sc = new Scanner(System.in);

        for (;;) {
            int input = 0;
            // System.out.print("挿入する数値を入力して下さい（負数で挿入終了）: ");
            input = sc.nextInt();
            if (input < 0) {
                break;
            }
            System.out.println("(" + input + ")を挿入");
            tree.insert(input);
            tree.printAll();
        }
        
        for (;;) {
            tree.printAll();
            // System.out.print("削除する数値を入力して下さい（負数で終了）: ");
            int input = sc.nextInt();
            if (input < 0) {
                break;
            }
            Integer deletedInteger = tree.delete(input);
            if (deletedInteger != null) {
                System.out.println("(" + deletedInteger + ")を削除");
            } else {
                System.out.println("(" + input + ")は存在しません");
            }
        }
    }
}