/* cs */
using System;
using System.Collections.Generic;

class Node<T> { 
  private T key;
  private Node<T> left, right;
  public Node(T key) {
    this.left = this.right = null;
    this.key = key;
  }
  
  public static void insertNode(ref Node<T> root, T key) {
  	insertNode(ref root, key, Comparer<T>.Default);
  }
  
  public static void insertNode(ref Node<T> root, T key, IComparer<T> comparer) {
    if (root == null) {
      root = new Node<T>(key);
      return;
    }
    if (comparer.Compare(key, root.key) < 0)
      insertNode(ref root.left, key, comparer);
    else
      insertNode(ref root.right, key, comparer);
  }
  
  public static bool deleteNode(ref Node<T> root, T key) {
  	return deleteNode(ref root, key, Comparer<T>.Default);
  }
  
  public static bool deleteNode(ref Node<T> root, T key, IComparer<T> comparer) {
    if (root == null) return false;
    if (comparer.Compare(key, root.key) < 0)
      return deleteNode(ref root.left, key, comparer);
    else if (comparer.Compare(key, root.key) > 0)
      return deleteNode(ref root.right, key, comparer);
    else {
      if (root.left == null) {
        root = root.right;
      } else if (root.right == null) {
        root = root.left;
      } else { // root.left != null && root.right != null
        Node<T> p;
        for (p = root.left; p.right != null; p = p.right)
          ;
        p.right = root.right;
        root = root.left;
      }
    }
    return true;
  }

  public void vomitTree(int c) {
    if (this.left != null)
      this.left.vomitTree(c + 3);
    for (int i = 0; i < c; i++) Console.Write(' ');
    Console.WriteLine(this.key);
    if (this.right != null)
      this.right.vomitTree(c + 3);
  }
}

class BinaryTree<T> {
  private Node<T> root;
  public BinaryTree() { this.root = null; }
  public void insertNode(T key) { Node<T>.insertNode(ref this.root, key); }
  public bool deleteNode(T key) { return Node<T>.deleteNode(ref this.root, key); } 
  public void vomitTree() { if (this.root != null) this.root.vomitTree(0); }
}

class Sample{
  public static void Main() {
    var tree = new BinaryTree<int>();
    for (;;) {
      Console.Write("> ");
      int input = int.Parse(Console.ReadLine());
      if (input < 0)
        break;
      tree.insertNode(input);
      tree.vomitTree();
    }
    Console.WriteLine("deleting.");
    for (;;) {
      Console.Write("> ");
      int input = int.Parse(Console.ReadLine());
      if (input < 0)
        break;
      if (tree.deleteNode(input))
        Console.WriteLine("deleted.");
      else
        Console.WriteLine("not found.");
      tree.vomitTree();
    }
  }
}
/* end */