class Tree
  attr_accessor :id,:parent,:children
  def initialize(id)
    @id=id
    @parent=-1
    @children=[nil,nil]
  end
  def preorder
    print " #{id}"
    children[0].preorder if children[0]
    children[1].preorder if children[1]
  end
  def inorder
    children[0].inorder if children[0]
    print " #{id}"
    children[1].inorder if children[1]
  end
end
def insert(id)
  z=Tree.new(id)
  y=nil
  x=$root
  while x
    y=x
    x= z.id < x.id ? x.children[0] : x.children[1]
  end
  unless y
    $root=z
  else
    z.id < y.id ?  y.children[0]=z : y.children[1]=z
  end
end
N=gets.to_i
N.times do
  cmd,id=gets.split
  case cmd
  when "insert" 
    insert(id.to_i)
  else
    $root.inorder
    puts ""
    $root.preorder
    puts ""
  end
end