abstract class Tree<A> {
  public abstract boolean contains((A, A) -> boolean less, A x);
  public abstract Tree<A> insert ((A, A) -> boolean less, A x);
}

class EmptyTree<A> extends Tree<A> {
  public boolean contains((A, A) -> boolean less, A x) {
    return false;
  }
  public Tree<A> insert((A, A) -> boolean less, A x) {
    return new Branch(x, this, this);
  }
}

class Branch<A> extends Tree<A> {
  A elem;
  Tree<A> left;
  Tree<A> right;
  
  public Branch(A elem, Tree<A> left, Tree<A> right) {
    this.elem = elem;
    this.left = left;
    this.right = right;
  }
  
  public boolean contains((A, A) -> boolean less, A x) {
    if (less(x, elem)) 
      return left.contains(less, x);
    else if (less(elem, x))
      return right.contains(less, x);
    else // we assume total ordering, therefore x.equals(elem)
      return true;
  }
  
  public Tree<A> insert((A, A) -> boolean less, A x) {
    if (less(x, elem)) 
      return new Branch(elem, left.insert(less, x), right);
    else if (less(elem, x))
      return new Branch(elem, left, right.insert(less, x));
    else 
      return this;
  }
}

class StringBranch extends Branch<String> {

  StringBranch(String elem, Tree<String> left, Tree<String> right) {
    super(elem, left, right);
  }

  private static boolean stringLess(String x, String y) {
    return x.compareTo(y) > 0;
  }
  
  public boolean contains(String x) {
    return contains(stringLess, x);
  }
  
  public Tree<String> insert(String x) {
    return insert(stringLess, x);
  }
}