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)
	{
		if (this == n)
			throw new IndexOutOfBoundsException();
		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 remove (int key)
	{
		if (getKey() == key)
		{
			if (getLeft() == null && getRight() == null)
			{
				removeNoChildren();
				return;
			}
			if (getLeft() == null || getRight() == null)
			{
				removeOneChild();
				return;
			}
			
			RBTNode t = getLeft();
			while (t.getRight() != null)
				t = t.getRight();
			
			setValue(t.getValue());
			setKey(t.getKey());
			t.remove(t.getKey());
		}
		else
		{
			if (key < getKey())
//			{
//				if (getLeft() == get
				getLeft().remove(key);
			else
				getRight().remove(key);
		}
	}
	
	public void removeOneChild ()
	{
		// 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.remove1();
		}
	}
	
	public void replaceNode (RBTNode n)
	{
		if (getParent() == null)
			tree.setRoot(n);
		else
		{
			if (getParent().getLeft() == this)
				getParent().setLeft(n);
			else
				getParent().setRight(n);
		}
	}

	public void removeNoChildren ()
	{
		if (getColor() == BLACK)
		{
			System.out.println(getSibling() + " " + 
			                   getParent().blackCount(getParent()) + " " + 
			                   tree.root.blackCount(getParent()));
			remove1();
		}
		
		if (this == getParent().getLeft())
			getParent().setLeft(null);
		else
			getParent().setRight(null);
	}
	
	public void remove1 ()
	{
		if (getParent() == null)
			return;
		remove2();
	}
	
	public void remove2 ()
	{
		System.out.println(getSibling());
		if (getSibling() != null && getSibling().getColor() == RED)
		{
			getParent().setColor(RED);
			getSibling().setColor(BLACK);
			if (this == getParent().getLeft())
				getParent().rotateLeft();
			else
				getParent().rotateRight();
		}
		remove3();
	}
	
	public void remove3 ()
	{
		if (getSibling() == null || getParent() == null)
			System.out.println(getColor() + " " + getSibling() + " " + getParent());
		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().remove1();
		}
		else
			remove4();
	}
	
	public void remove4 ()
	{
		if (getParent().getColor() == RED && 
		    getSibling().getColor() == BLACK && 
		    (getSibling().getLeft() == null || getSibling().getLeft().getColor() == BLACK) && 
		    (getSibling().getRight() == null || getSibling().getRight().getColor() == BLACK))
		{
			getSibling().setColor(RED);
			getParent().setColor(BLACK);
		}
		else
			remove5();
	}
	
	public void remove5 ()
	{
		if (this == getParent().getLeft() && 
		    getSibling().getColor() == BLACK && 
		    (getSibling().getLeft() != null && getSibling().getLeft().getColor() == RED) && 
		    (getSibling().getRight() == null || getSibling().getRight().getColor() == BLACK))
		{
			getSibling().setColor(RED);
			getSibling().getLeft().setColor(BLACK);
			getSibling().rotateRight();
		}
		else if (this == getParent().getRight() && 
		         getSibling().getColor() == BLACK && 
		         (getSibling().getRight() != null && getSibling().getRight().getColor() == RED) && 
		         (getSibling().getLeft() == null || getSibling().getLeft().getColor() == BLACK))
		{
			getSibling().setColor(RED);
			getSibling().getRight().setColor(BLACK);
			getSibling().rotateLeft();
		}
		remove6();
	}
	
	public void remove6 ()
	{
		getSibling().setColor(getParent().getColor());
		getParent().setColor(BLACK);
		if (this == getParent().getLeft())
		{
			getSibling().getRight().setColor(BLACK);
			getParent().rotateLeft();
		}
		else
		{
			getSibling().getLeft().setColor(BLACK);
			getParent().rotateRight();
		}
	}

	public int getHeight ()
	{
		if (getLeft() == this)
			System.out.println("oh no");
		if (getRight() == this)
			System.out.println("no oh");
		int out = 1;
		if (getLeft() != null)
			out = 1 + getLeft().getHeight();
		if (getRight() != null)
			out = Math.max(out, 1 + getRight().getHeight());
		return out;
	}

	public boolean check4 ()
	{
		if (getColor() == RED && (getParent().getColor() == RED || 
		                          getLeft() != null && getLeft().getColor() == RED || 
					  getRight() != null && getRight().getColor() == RED))
			return false;

		if (getLeft() != null && !getLeft().check4())
			return false;
		if (getRight() != null && !getRight().check4())
			return false;
		return true;
	}
	
	public boolean check5 ()
	{
		return check5(null);
	}
	
	public boolean check5 (RBTNode n)
	{
		if (getLeft() == null)
			return getRight() == null || getRight().getColor() == RED;
		if (getRight() == null)
			return getLeft().getColor() == RED;
		System.out.println("-----------");
		return blackCount(n) != -1;
	}
	
	public int blackCount ()
	{
		return blackCount(null);
	}

	public int blackCount (RBTNode n)
	{
		if (this == n)
			System.out.println("MEEEP");
		int left = 0, right = 0;
		if (getLeft() != null)
			left = getLeft().blackCount(n);
		if (getRight() != null)
			right = getRight().blackCount(n);
		System.out.println(left + " * " + right);
		
		if (left == -1 || right == -1 || left != right)
			return -1;
		return left + (getColor() == BLACK ? 1 : 0);
	}
}

public class RedBlackTree
{
	private int size;
	public 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 remove (int key)
	{
		if (size >= 1)
		{
			boolean cond2 = root.getColor() == false;
			boolean cond4 = root.check4();
			boolean cond5 = root.check5();
			System.out.println(true + " " + cond2 + " " + true + " " + cond4 + " " + cond5);
		}
		if (size == 1)
			root = null;
		else
			root.remove(key);
		size--;
	}
	
	public int getHeight ()
	{
		if (root == null)
			return 0;
		return root.getHeight();
	}
}