import java.util.*;

class RBTNode
{
	private static final boolean RED, BLACK;
	static
	{
		RED = true;
		BLACK = false;
	}
	
	private boolean color;
	private RBTNode left, right, parent;
	private int key, value;
	private RedBlackTree tree;

	public RBTNode (int inKey, int inValue, RedBlackTree inTree)
	{
		setKey(inKey);
		setValue(inValue);
		tree = inTree;
		setColor(RED);
	}
	
	public int getValue ()
	{
		return value;
	}

	public void setValue (int inValue)
	{
		value = inValue;
	}

	public int getKey ()
	{
		return key;
	}

	public void setKey (int inKey)
	{
		key = inKey;
	}
	
	public boolean getColor ()
	{
		return color;
	}
	
	public void setColor (boolean c)
	{
		color = c;
	}
	
	public RBTNode getLeft ()
	{
		return left;
	}
	
	public void setLeft (RBTNode n)
	{
		left = n;
	}
	
	public RBTNode getRight ()
	{
		return right;
	}
	
	public void setRight (RBTNode n)
	{
		right = n;
	}
	
	public RBTNode getParent ()
	{
		return parent;
	}

	public void setParent (RBTNode n)
	{
		parent = n;
	}
	
	public RBTNode getGrandparent ()
	{
		return getParent().getParent();
	}
	
	public RBTNode getUncle ()
	{
		if (getParent() == getGrandparent().getLeft())
			return getGrandparent().getRight();
		else
			return getGrandparent().getLeft();
	}
	
	public RBTNode getSibling ()
	{
		if (this == getParent().getLeft())
			return getParent().getRight();
		return getParent().getLeft();
	}

	public boolean isLeaf ()
	{
		return getLeft() == null && getRight() == null;
	}
	
	public int get (int key)
	{
		if (key == getKey())
			return getValue();
		if (key < getKey())
			return getLeft().get(key);
		return getRight().get(key);
	}

	public void insert (RBTNode n)
	{
		if (n.getKey() <= getKey())
		{
			if (left == null)
			{
				setLeft(n);
				n.setParent(this);
				n.insert1();
			}
			else
				left.insert(n);
		}
		else
		{
			if (right == null)
			{
				setRight(n);
				n.setParent(this);
				n.insert1();
			}
			else
				right.insert(n);
		}
	}
	
	public void insert1 ()
	{
		if (getParent() == null)
			setColor(BLACK);
		else
			insert2();
	}
	
	public void insert2 ()
	{
		if (getParent().getColor() == BLACK)
			return;
		else
			insert3();
	}
	
	public void insert3 ()
	{
		if (getUncle() != null && getUncle().getColor() == RED)
		{
			getParent().setColor(BLACK);
			getUncle().setColor(BLACK);
			getGrandparent().setColor(RED);
			getGrandparent().insert1();
		}
		else
			insert4();
	}
	
	public void insert4 ()
	{
		RBTNode next = this;
		if (this == getParent().getRight() && getParent() == getGrandparent().getLeft())
		{
			getParent().rotateLeft();
			next = getLeft();
		}
		else if (this == getParent().getLeft() && getParent() == getGrandparent().getRight())
		{
			getParent().rotateRight();
			next = getRight();
		}
		next.insert5();
	}
	
	public void insert5 ()
	{
		getParent().setColor(BLACK);
		getGrandparent().setColor(RED);
		if (this == getParent().getLeft() && getParent() == getGrandparent().getLeft())
			getGrandparent().rotateRight();
		else
			getGrandparent().rotateLeft();
	}
	
	public void rotateLeft ()
	{
		RBTNode t = getRight();
		setRight(t.getLeft());
		if (t.getLeft() != null)
			t.getLeft().setParent(this);
		
		t.setParent(getParent());
		if (getParent() == null)
			tree.setRoot(t);
		else if (this == getParent().getLeft())
			getParent().setLeft(t);
		else
			getParent().setRight(t);
		
		t.setLeft(this);
		setParent(t);

		if (t.getParent() == null)
			tree.setRoot(t);
	}
	
	public void rotateRight ()
	{
		RBTNode t = getLeft();
		setLeft(t.getRight());
		if (t.getRight() != null)
			t.getRight().setParent(this);
		
		t.setParent(getParent());
		if (getParent() == null)
			tree.setRoot(t);
		else if (this == getParent().getRight())
			getParent().setRight(t);
		else
			getParent().setLeft(t);
		
		t.setRight(this);
		setParent(t);

		if (t.getParent() == null)
			tree.setRoot(t);
	}
	
	public void delete (int key)
	{
		if (getKey() == key)
		{
			if (getLeft() == null && getRight() == null)
			{
				deleteNoChildren();
				return;
			}
			if (getLeft() == null || getRight() == null)
			{
				deleteOneChild();
				return;
			}
			
			RBTNode t = getLeft();
			while (t.getRight() != null)
				t = t.getRight();
			
			setValue(t.getValue());
			setKey(t.getKey());
			t.delete(t.getKey());
		}
		else
		{
			if (key < getKey())
				getLeft().delete(key);
			else
				getRight().delete(key);
		}
	}
	
	public void deleteOneChild ()
	{
		// n has at most one non-null child
		RBTNode t = getRight() == null ? getLeft() : getRight();
		replaceNode(t);
		if (getColor() == BLACK)
		{
			if (t.getColor() == RED)
				t.setColor(BLACK);
			else
				t.delete1();
		}
	}
	
	public void replaceNode (RBTNode n)
	{
		if (n != null)
		{
			n.setParent(getParent());
			if (getRight() == null)
			{
				n.setLeft(getLeft());
				n.setRight(null);
			}
			else
			{
				n.setLeft(null);
				n.setRight(getRight());
			}
		}
		
		if (n.getParent() == null)
			tree.setRoot(n);
	}

	public void deleteNoChildren ()
	{
		if (getColor() == BLACK)
			delete1();

		if (this == getParent().getLeft())
			getParent().setLeft(null);
		else
			getParent().setRight(null);
	}
	
	public void delete1 ()
	{
		if (getParent() == null)
			return;
		delete2();
	}
	
	public void delete2 ()
	{
		if (getSibling() != null && getSibling().getColor() == RED)
		{
			getParent().setColor(RED);
			getSibling().setColor(BLACK);
			if (this == getParent().getLeft())
				getParent().rotateLeft();
			else
				getParent().rotateRight();
		}
		delete3();
	}
	
	public void delete3 ()
	{
		if (getParent().getColor() == BLACK && 
		    getSibling().getColor() == BLACK && 
		    (getSibling().getLeft() == null || getSibling().getLeft().getColor() == BLACK) && 
		    (getSibling().getRight() == null || getSibling().getRight().getColor() == BLACK))
		{
			getSibling().setColor(RED);
			getParent().delete1();
		}
		else
			delete4();
	}
	
	public void delete4 ()
	{
		if (getParent().getColor() == BLACK && 
		    getSibling().getColor() == BLACK && 
		    getSibling().getLeft().getColor() == BLACK && 
		    getSibling().getRight().getColor() == BLACK)
		{
			getSibling().setColor(RED);
			getParent().setColor(BLACK);
		}
		else
			delete5();
	}
	
	public void delete5 ()
	{
		if (this == getParent().getLeft() && 
		    getSibling().getColor() == BLACK && 
		    getSibling().getLeft().getColor() == RED && 
		    getSibling().getRight().getColor() == BLACK)
		{
			getSibling().setColor(RED);
			getSibling().getLeft().setColor(BLACK);
			getSibling().rotateRight();
		}
		else if (this == getParent().getRight() && 
		    getSibling().getColor() == BLACK && 
		    getSibling().getRight().getColor() == RED && 
		    getSibling().getLeft().getColor() == BLACK)
		{
			getSibling().setColor(RED);
			getSibling().getRight().setColor(BLACK);
			getSibling().rotateLeft();
		}
		delete6();
	}
	
	public void delete6 ()
	{
		getSibling().setColor(getParent().getColor());
		getParent().setColor(BLACK);
		if (this == getParent().getLeft())
		{
			getSibling().getRight().setColor(BLACK);
			getParent().rotateLeft();
		}
		else
		{
			if (getSibling().getLeft() != null)
				getSibling().getLeft().setColor(BLACK);
			getParent().rotateRight();
		}
	}

	public int getHeight ()
	{
		int out = 1;
		if (getLeft() != null)
			out = 1 + getLeft().getHeight();
		if (getRight() != null)
			out = Math.max(out, 1 + getRight().getHeight());
		return out;
	}
}

public class RedBlackTree
{
	private int size;
	private RBTNode root;

	public RedBlackTree ()
	{
		size = 0;
		root = null;
	}
	
	public void setRoot (RBTNode n)
	{
		root = n;
	}
	
	public int getSize ()
	{
		return size;
	}
	
	public int get (int key)
	{
		return root.get(key);
	}
	
	public void insert (int key, int value)
	{
		RBTNode n = new RBTNode(key, value, this);
		if (root == null)
		{
			root = n;
			root.insert1();
		}
		else
			root.insert(n);
		
		size++;
	}
	
	public void delete (int key)
	{
		if (size == 1)
			root = null;
		else
			root.delete(key);
		size--;
	}
	
	public int getHeight ()
	{
		if (root == null)
			return 0;
		return root.getHeight();
	}
}