class Node
  attr_reader :value

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  def insert(value)
    if value < @value
      if @left
        @left.insert(value)
      else
        @left = Node.new(value)
      end
    else
      if @right
        @right.insert(value)
      else
        @right = Node.new(value)
      end
    end
  end

  def visit_inorder(&block)
    @left.visit_inorder(&block) if @left
    block.call(self) if block
    @right.visit_inorder(&block) if @right
  end

  def visit_preorder(&block)
    block.call(self) if block
    @left.visit_preorder(&block) if @left
    @right.visit_preorder(&block) if @right
  end
end

if $PROGRAM_NAME == __FILE__
  n = gets.to_i

  root = nil

  n.times do
    command = gets.chomp

    case command
    when /^insert\s+(\d+)/
      value = $1.to_i

      if root
        root.insert(value)
      else
        root = Node.new(value)
      end
    when 'print'
      root.visit_inorder do |node|
        print " #{node.value}"
      end
      puts

      root.visit_preorder do |node|
        print " #{node.value}"
      end
      puts
    end
  end
end