#include <iostream>
#include <new>

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

struct supernode {
  int id;
  unsigned int size;
  void *data;
  struct supernode *next;
  struct supernode *before;
};

void xmallocdump(void);
void *xmalloc(unsigned int, int);
void xfree(void *, int);
void *xrealloc(void *, unsigned int, int);

static struct supernode *superrootS = NULL;

#define N 16
void xmallocdump(void)
{
  int i;
  unsigned char c;
  struct supernode *p;
  if (superrootS == NULL) {
    fprintf(stderr, "xmallocdump(): root is NULL.\n"); fflush(stderr);
  } else {
    p = superrootS;
    fprintf(stderr, "ERROR: Memory leak occured!\n");
    do {
      fprintf(stderr, "Memory Leak >%p %p %p(%d):%d: ", (void *)p, (void *)p->next, (void *)p->data, p->size, p->id);
      for (i = 0; i < N; i++) {
        c = *(unsigned char *)((char *)(p->data) + i);
        printf("%02x(%c) ", c , (isprint(c)) ? c : '.');
      }
      putchar('\n');
      p = p->next;
    } while (p != superrootS);
  }
}

void *xmalloc(unsigned int n, int id)
{
  unsigned int i;
  struct supernode *p;
  rand();
  if (!(p = (struct supernode *)malloc(sizeof(struct supernode)))) {
    fprintf(stderr, "xmalloc(): cannot malloc() in xmalloc()\n");
    abort();
  }
  if (superrootS == NULL) {
    superrootS = p;
    p->size = n;
    p->next = p;
    p->before = p;
  } else {
    p->size = n;
    p->next = superrootS->next;
    p->before = superrootS;
    superrootS->next = p;
    p->next->before = p;
  }
  if (!(p->data = malloc(n))) {
    fprintf(stderr, "xmalloc(): cannot malloc() in malloc()\n");
    abort();
  } else {
    /* nothing */
  }
  for (i = 0; i < n; i++)
    *(char *)((char *)(p->data) + i) = rand() & 0xff;
  p->id = id;
/*printf("xmalloc():malloc id = %d(%p)\n", p->id, p->data); */
  return p->data;
}

void xfree(void *p, int id)
{
  unsigned int flag, i;
  struct supernode *q;
  /*printf("xfree():free id = %d(%p)\n", id, p); */
  if (p == NULL)
    return;
  if (superrootS == NULL) {
    fprintf(stderr, "xfree(): root is null.\n");
    abort();
  }
  rand();
  flag = 0;
  q = superrootS;
  for (;;) {
    if (q->data == p) {
      if (q->id != id) {
        fprintf(stderr, "xfree(): bad ID. %d <- %d\n", q->id, id);
        abort();
      }
      if (q->next == q) {
        for (i = 0; i < q->size; i++)
          *(char *)((char *)(q->data) + i) = rand() & 0xff;
        free(q->data);
        free(q);
        flag = 1;
        superrootS = NULL;
        break;
      } else {
        q->before->next = q->next;
        q->next->before = q->before;
        if (q == superrootS)
          superrootS = q->next;
        for (i = 0; i < q->size; i++)
          *(char *)((char *)(q->data) + i) = rand() & 0xff;
        free(q->data);
        free(q);
        flag = 1;
        break;
      }
    }
    if (q->next == superrootS)
      break;
    q = q->next;
  }
  if (flag != 1) {
    fprintf(stderr, "xfree(): cannot xfree(), no data.(id = %d, %p)\n", id, p);
    abort();
  }
}

/*------------------*/
#define ID_NODE  1001
/*------------------*/


template <class T>
class Node {
private:
  T key;
  Node *left, *right;
public:
  Node(T key) {
    this->left = this->right = nullptr;
    this->key = key;
  }    

  void *operator new(size_t size) { return xmalloc(size, ID_NODE); }
  void operator delete(void *p) { xfree(p, ID_NODE); }

  static void insertNode(Node<T> *&root, T key) {
    if (root == nullptr) {
      root = new Node<T>(key);
      return;
    }
    if (key < root->key)
      insertNode(/*ref*/root->left, key);
    else
      insertNode(/*ref*/root->right, key);
  }


  static bool deleteNode(Node<T> *&root, T key) {
    if (root == nullptr) return false;
    if (key < root->key)
      return deleteNode(/*ref*/root->left, key);
    else if (key > root->key)
      return deleteNode(/*ref*/root->right, key);
    else {
      if (root->left == nullptr) {
        Node<T> *p;
        p = root;
        root = root->right;
        delete p;
      } else if (root->right == nullptr) {
        Node *p;
        p = root;
        root = root->left;
        delete p;
      } else { // root->left != 0 && root->right != 0
        Node *p, *q;
        for (p = root->left; p->right != nullptr; p = p->right)
          ;
        p->right = root->right;
        q = root;
        root = root->left;
        delete q;
      }
    }
    return true;
  }

#if defined(N)
#undef N
#endif
#define N 3

  void vomitTree(int c) {
    if (this == nullptr)
      return;
    this->left->vomitTree(c + N);
    for (int i = 0; i < c; i++) std::cout << ' ';
    std::cout << this->key << std::endl;
    this->right->vomitTree(c + N);
  }
  
  static void release(Node<T> *&root) {
    if (root != nullptr) {
      release(/*ref*/root->left);
      release(/*ref*/root->right);
      delete root;
      root = nullptr;
    }
  }

};

template <class T>
class BinaryTree {
private:
  Node<T> *root;
public:
  BinaryTree<T>() { this->root = nullptr; }
  ~BinaryTree<T>() { Node<T>::release(/*ref*/this->root); }
  void insertNode(T key) { try { Node<T>::insertNode(/*ref*/this->root, key);
                         } catch (std::bad_alloc) { std::cerr << "memory full." << std::cerr; }
  }
  bool deleteNode(T key) { return Node<T>::deleteNode(/*ref*/this->root, key); }
  void vomitTree() { this->root->vomitTree(0); }
};

int main() {
  auto tree = new BinaryTree<int>();
  for (;;) {
    auto input = 0;
    //std::cout << "> ";
    std::cin >> input;
    if (input < 0)
      break;
    tree->insertNode(input);
    tree->vomitTree();
  }
  std::cout << "deleting" << std::endl;
  for (;;) {
    auto input = 0;
    //std::cout << "> ";
    std::cin >> input;
    if (input < 0)
      break;
    if (tree->deleteNode(input))
      std::cout << "deleted." << std::endl;
    else
      std::cout << "not found." << std::endl;
    tree->vomitTree();
  }
  delete tree;
  xmallocdump();
}
/* end */