class Node
  attr_accessor :key, :left, :right, :parent
  def initialize key
    @key = key
  end
  def extract
    if right
      right.extract
    else
      puts $key=key
      delete $root
    end
  end
  def in
    left.in if left
    $a << self
  end
end

def insert
  z = Node.new $key
  x = $root
  while x
    y = x
    x = z.key < x.key ? x.left : x.right
  end
  z.parent=y
  unless y
    $root = z
  else
    z.key < y.key ? y.left = z : y.right = z
  end
end

def find root
  if root == nil
    puts 'no'
  elsif $key == root.key
    puts 'yes'
  elsif $key < root.key
    find root.left
  else
    find root.right
  end
end

def delete1 parent, node
  if parent
    if l = parent.left
      $key == l.key ? parent.left = node : parent.right = node
    else
      parent.right = node
    end
  else
    $root = node
  end
  node.parent = parent
end
def delete root
  left = root.left
  right = root.right
  if $key == root.key
    parent = root.parent
    if (left || right) == nil
      if l = parent.left
        $key == l.key ? parent.left = nil : parent.right = nil
      else
        parent.right = nil
      end
    elsif left && right
      $a=[]
      right.in
      root.key = $key = $a[0].key
      delete $a[0]
    elsif left
      delete1 parent, left
    else
      delete1 parent, right
    end
  elsif $key < root.key
    delete left
  else
    delete right
  end
end

begin
  command, $key = gets.split
  $key = $key.to_i
  case command
  when 'insert'
    insert
  when 'extract'
    $root.extract
  end
end while command != 'end'