import java.util.*;

class SplayNode
{
	private SplayNode left, right, parent;
	private int key, value;
	private SplayTree tree;

	public SplayNode (int inKey, int inValue, SplayTree inTree)
	{
		setKey(inKey);
		setValue(inValue);
		tree = inTree;
	}
	
	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 SplayNode getLeft ()
	{
		return left;
	}
	
	public void setLeft (SplayNode n)
	{
		if (this == n)
			throw new IndexOutOfBoundsException();
		left = n;
	}
	
	public SplayNode getRight ()
	{
		return right;
	}
	
	public void setRight (SplayNode n)
	{
		if (this == n)
			throw new IndexOutOfBoundsException();
		right = n;
	}
	
	public SplayNode getParent ()
	{
		return parent;
	}

	public void setParent (SplayNode n)
	{
		parent = n;
	}
	
	public SplayNode getGrandparent ()
	{
		return getParent().getParent();
	}
	
	public boolean isLeaf ()
	{
		return getLeft() == null && getRight() == null;
	}
	
	public int get (int key)
	{
		if (key == getKey())
		{
			splay();
			return getValue();
		}
		if (key < getKey())
			return getLeft().get(key);
		return getRight().get(key);
	}

	public void insert (SplayNode n)
	{
		if (n.getKey() <= getKey())
		{
			if (left == null)
			{
				setLeft(n);
				n.setParent(this);
				n.splay();
			}
			else
				left.insert(n);
		}
		else
		{
			if (right == null)
			{
				setRight(n);
				n.setParent(this);
				n.splay();
			}
			else
				right.insert(n);
		}
	}
	
	public void remove (int key)
	{
		if (getKey() == key)
		{
			if (getLeft() == null && getRight() == null)
			{
				if (getParent().getLeft() == this)
					getParent().setLeft(null);
				else
					getParent().setRight(null);
			}
			else if (getLeft() == null || getRight() == null)
			{
				SplayNode t = (getLeft() == null ? getRight() : getLeft());
				if (getParent() == null)
					tree.setRoot(t);
				else if (getParent().getLeft() == this)
					getParent().setLeft(t);
				else
					getParent().setRight(t);
				t.setParent(getParent());
			}
			else
			{
				SplayNode t = getLeft();
				while (t.getRight() != null)
					t = t.getRight();
				
				setValue(t.getValue());
				setKey(t.getKey());
				t.remove(t.getKey());
			}
		}
		else
		{
			if (key < getKey())
				getLeft().remove(key);
			else
			{
				if (getRight() == null)
					 tree.root.get(key);
				getRight().remove(key);
			}
		}
	}
	
	public void splay ()
	{
		if (getParent() == null)
		{
			tree.setRoot(this);
		}
		else if (getParent().getParent() == null)
		{
			tree.setRoot(this);
			if (getParent().getLeft() == this)
			{
				getParent().setLeft(getRight());
				if (getRight() != null)
					getRight().setParent(getParent());
				setRight(getParent());
				getParent().setParent(this);
			}
			else
			{
				getParent().setRight(getLeft());
				if (getLeft() != null)
					getLeft().setParent(getParent());
				setLeft(getParent());
				getParent().setParent(this);
			}
			setParent(null);
		}
		else
		{
			if (getParent().getParent().getLeft() == getParent())
			{
				if (getParent().getLeft() == this)
				{
					getParent().getParent().setLeft(getParent().getRight());
					if (getParent().getParent().getLeft() != null)
						getParent().getParent().getLeft().setParent(getParent().getParent());
					getParent().setRight(getParent().getParent());
					getParent().setLeft(getRight());
					if (getParent().getLeft() != null)
						getParent().getLeft().setParent(getParent());
					setRight(getParent());
					
					SplayNode t = getParent();
					setParent(getParent().getParent().getParent());
					t.getParent().setParent(t);
					t.setParent(this);
				}
				else
				{
					getParent().setRight(getLeft());
					if (getLeft() != null)
						getLeft().setParent(getParent());
					getParent().getParent().setLeft(getRight());
					if (getRight() != null)
						getRight().setParent(getParent().getParent());
					
					setLeft(getParent());
					setRight(getParent().getParent());
					
					SplayNode t = getParent();
					setParent(getParent().getParent().getParent());
					t.getParent().setParent(this);
					t.setParent(this);
				}
			}
			else
			{
				if (getParent().getRight() == this)
				{
					getParent().getParent().setRight(getParent().getLeft());
					if (getParent().getParent().getRight() != null)
						getParent().getParent().getRight().setParent(getParent().getParent());
					getParent().setLeft(getParent().getParent());
					getParent().setRight(getLeft());
					if (getParent().getRight() != null)
						getParent().getRight().setParent(getParent());
					setLeft(getParent());
					
					SplayNode t = getParent();
					setParent(getParent().getParent().getParent());
					t.getParent().setParent(t);
					t.setParent(this);
				}
				else
				{
					getParent().setLeft(getRight());
					if (getRight() != null)
						getRight().setParent(getParent());
					getParent().getParent().setRight(getLeft());
					if (getLeft() != null)
						getLeft().setParent(getParent().getParent());
					
					setRight(getParent());
					setLeft(getParent().getParent());
					
					SplayNode t = getParent();
					setParent(getParent().getParent().getParent());
					t.getParent().setParent(this);
					t.setParent(this);
				}
			}		
			splay();
		}
	}

	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 SplayTree
{
	private int size;
	public SplayNode root;

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