public class BST<Key extends Comparable<Key>, Value>
{

    private Node root;

    private class Node
    {
        Key key;
        Value val;
        Node left, right;
        Node(Key key, Value val)
        { this.key = key; this.val = val;}
    }

public Value get(Key key)
{ return get(root, key);}


private Value get(Node x, Key key)
{
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) return get(x.left, key);
    else if (cmp > 0) return get(x.right, key);
    else return x.val;
}

public boolean contains(Key key)
{ return (get(key) != null); }

public void put(Key key, Value val)
{ root = put(root, key, val); }

private Node put(Node x, Key key, Value val)
{
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else x.val = val;
    return x;
}

public static void main(String ar[])
    {
   
    }


}