class BinSearchTree
  attr_accessor :node
  def initialize()
    @node = []
  end
  def preorder(n=root())
    arr = []
    return [] if n == nil || n < 0
    #root
    arr += [node[n].key]
    #left
    arr += preorder(node[n].left)
    #right
    arr += preorder(node[n].right)
    return arr
  end
  def inorder(n=root())
    arr = []
    return [] if n == nil || n < 0 
    #left
    arr += inorder(node[n].left)
    #root
    arr += [node[n].key]
    #right
    arr += inorder(node[n].right)
    return arr
  end
  def root
    #find root
    r = nil
    node.size.times {|i|
      if node[i].parent == -1 then
        r = i
        break
      end
    }
    return r
  end
  def insert(z)
    n = node.size
    node[n] = Node.new()
    node[n].key = z
    y = nil
    x = root()
    while x != nil
      y = x
      if node[n].key < node[x].key
        x = node[x].left
      else
        x = node[x].right
      end
    end
    node[n].parent = y
    if y == nil then
      node[n].parent = -1
    elsif node[n].key < node[y].key
      node[y].left = n
    else
      node[y].right = n
    end
  end
  def print
    str = inorder().join(" ")
    puts " #{str}"
    str = preorder().join(" ")
    puts " #{str}"
  end
end

class Node
  attr_accessor :key, :parent, :left, :right
  def initialize
    @key = nil
    @parent = nil
    @left = nil
    @right = nil
  end
end

n = gets.to_i
tree = BinSearchTree.new()

n.times{
  command, num = gets.split
  case command;
  when "insert"; tree.insert(num)
  when "print"; tree.print
  end
}