import java.util.Scanner;

public class Driver
{
  public static void main(String[] args)
  {
    topdownRB tree=new topdownRB(0);
    Scanner sc=new Scanner(System.in);

    while (true)
    {
      int target1,target2;
      ITEM result;
      switch (sc.nextInt())
      {
        case 0:
          System.out.format("0: exit\n");
          return;
        case 1:
          target1=sc.nextInt();
          if (tree.search(new myKey(target1))==null)
          {
            tree.insert(new myItem(target1,target1));
            System.out.format("1: %d inserted\n",target1);
          }
          else
            System.out.format("1: %d is a duplicate key\n",target1);
          break;
        case 2:
          target1=sc.nextInt();
          result=tree.searchFirstKeyNotLessThan(new myKey(target1));
          if (result==null)
            System.out.format("2: %d is too large\n",target1);
          else
            System.out.format(
              "2: %s is the smallest key not smaller than %d\n",
               result.key().toString(),target1);
          break;
        case 3:
          target1=sc.nextInt();
          result=tree.searchLastKeyNotGreaterThan(new myKey(target1));
          if (result==null)
            System.out.format("3: %d is too small\n",target1);
          else
            System.out.format(
              "3: %s is the largest key not larger than %d\n",
               result.key().toString(),target1);
          break;
        case 4:
          target1=sc.nextInt();
          target2=sc.nextInt();
          System.out.format("4: keys between %d and %d:",target1,target2);
          tree.traverseBetween(new myKey(target1),new myKey(target2));
          System.out.format("\n");
          break;
        case 5:
          target1=sc.nextInt();
          if (tree.search(new myKey(target1))==null)
            System.out.format("5: %d not in tree\n",target1);
          else
            System.out.format("5: %d has rank %d\n",target1,
              tree.rank4key(new myKey(target1)));
          break;
        case 6:
          target1=sc.nextInt();
          KEY resultKey=tree.key4rank(target1);
          if (resultKey==null)
            System.out.format("6: requested rank %d is outside range\n",
              target1);
          else
            System.out.format("6: rank %d is for key %s\n",target1,
              resultKey.toString());
          break;
        case 7:
          if (tree.auditSizes())
            System.out.format("7: clean\n");
          else
            System.out.format("7: corrupt\n");
          break;
        default:
          System.out.println("Bad input");
          return;
      } // switch
    } // while
  } // main
} // Driver