
class BinaryTree
  def initialize
    @tree = nil
    @fun = lambda { |key| printf(" %d", key)}
  end

  def insert(key)
    if @tree.nil?
      @tree = { key: key, left: nil, right: nil}
    else
      node = @tree
      par = @tree
      while not node.nil?
        par = node
        if key < node[:key]
          node = node[:left]
        else
          node = node[:right]
        end
      end
      par[:left] = { key: key, left: nil, right: nil} if key < par[:key]
      par[:right] = { key: key, left: nil, right: nil} if key >= par[:key]
    end
  end

  def print
    inorder
    preorder
  end

  def inorder
    inorder_help(@tree)
    puts
  end

  def preorder
    preorder_help(@tree)
    puts
  end

  def postorder
    postorder_help(@tree)
    puts
  end

  private
  def leaf?(node)
    node[:left].nil? and node[:right].nil?
  end

  def inorder_help(root)
    unless root.nil?
      inorder_help(root[:left])
      @fun.call(root[:key])
      inorder_help(root[:right])
    end
  end

  def preorder_help(root)
    unless root.nil?
      @fun.call(root[:key])
      preorder_help(root[:left])
      preorder_help(root[:right])
    end
  end

  def postorder_help(fun, root)
    unless root.nil?
      postorder_help(root[:left])
      postorder_help(root[:right])
      @fun.call(root[:key])
    end
  end
end

def main
  bt = BinaryTree.new
  n = gets.to_i
  n.times.each do |i|
    command, num = gets.split(/\s/)
    num = num.to_i
    bt.insert(num) if command == "insert"
    bt.print if command == "print"
  end
end

main