import java.io.*;
import java.util.*;

public class RBTreeTest
{
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		RedBlackTree tree = new RedBlackTree();
		LinkedList<Integer> keys = new LinkedList<Integer>();
		while (true)
		{
			String[] in = br.readLine().split(" ");
			
			switch (in[0].charAt(0))
			{
				case 'i':
				{
					keys.add(Integer.parseInt(in[1]));
					tree.insert(Integer.parseInt(in[1]), Integer.parseInt(in[2]));
					break;
				}
				case 'd':
				{
					if (in[0].length() == 2 && in[0].charAt(1) == 'b')
					{
						int t = Integer.parseInt(in[1]);
						for (int i = 0; i < t; i++)
							tree.remove(keys.remove((int)(Math.random()*keys.size())));
					}
					else
						tree.remove(Integer.parseInt(in[1]));
					break;
				}
				case 'g':
				{
					System.out.println(tree.get(Integer.parseInt(in[1])));
					break;
				}
				case 'p':
				{
					for (int i : keys)
						System.out.print(tree.get(i) + " ");
					System.out.println();
					break;
				}
				case 'h':
				{
					System.out.println(tree.getHeight());
					break;
				}
				case 'r':
				{
					int num = Integer.parseInt(in[1]);
					for (int i = 0; i < num; i++)
					{
						int t = (int)(Math.random()*100);
						keys.add(t);
						tree.insert(t, (int)(Math.random()*100));
					}
					break;
				}
				case 'o':
				{
					int num = Integer.parseInt(in[1]);
					for (int i = 0; i < num; i++)
					{
						keys.add(0);
						int t = (int)(Math.random()*100);
						tree.insert(0, t);
						System.out.print(t + " ");
					}
					System.out.println();
					break;
				}
				case 's':
				{
					System.out.println(tree.getSize() + " " + keys.size());
					break;
				}
				case 'q':
				{
					return;
				}
			}
		}
	}
}