class Graph
  include Comparable
  attr_reader :id, :depth, :value
  @@nodes = Array.new
  def initialize(id, left = nil, right = nil, value = nil)
    @id = id
    @left = left == -1? nil: left
    @right = right == -1? nil: right
    @depth = -1
    @parent = -1
    @sibling = -1
    @value = value ? value:id
    @@nodes[id] = self
  end
  
  def to_i
    return @value
  end
  
  def degree
    deg = 0
    deg += 1 if @left
    deg += 1 if @right
    return deg
  end
  
  def set_num(other)
    if @parent != -1
      if @left == other
        @parent.set_num(self) * 2
      elsif @right == other
        @parent.set_num(self) * 2 + 1
      end
    else
      1
    end
  end
  
  def num
    if @parent != -1
      @parent.set_num(self)
    else
      return 1
    end
  end
  
  def set_left(other)
    @left = other
  end
  
  def set_right(other)
    @right = other
  end
  
  def set_parent(other)
    @parent = other
  end
  
  def set_child
    @@nodes[@left].set_parent(self) if @left
    @@nodes[@right].set_parent(self) if @right
    if @left and @right
      @@nodes[@left].set_sib(@@nodes[@right])
      @@nodes[@right].set_sib(@@nodes[@left])
    end
  end
  
  def set_children
    set_child
    @@nodes[@left].set_children if @left
    @@nodes[@right].set_children if @right
  end
  
  def set_sib(other)
    @sibling = other
  end
  
  def insert(other)
    if @@nodes.length != 2
      if @value > other.value
        if @left
          @@nodes[@left].insert(other)
        else
          @left = other.id
          set_child
        end
      else
        if @right
          @@nodes[@right].insert(other)
        else
          @right = other.id
          set_child
        end
      end
    end
  end
  
  def print
    puts " " + inorder([], false).join(" ")
    puts " " + preorder([], false).join(" ")
  end
  
  def depth
    if @parent != -1
      @parent.depth + 1
    else
      0
    end
  end
  
  def height
    left = @left? @@nodes[@left].height: -1
    right = @right? @@nodes[@right].height: -1
    if left < right
      right + 1
    else
      left + 1
    end
  end
  
  def <=>(other)
    if Graph === other
      @value <=> other.value
    else
      @value <=> other
    end
  end
  
  def type
    if @parent == -1
      return "root"
    elsif degree == 0
      return "leaf"
    else
      return "internal node"
    end
  end
  
  def order(n, bool = true)
    if n == 0
      return ["Preorder", " " + preorder([], bool).join(" ")]
    elsif n == 1
      return ["Inorder", " " + inorder([], bool).join(" ")]
    else
      return ["Postorder", " " + postorder([], bool).join(" ")]
    end
  end
  
  def preorder(arr, bool = true)
    if bool
      arr << @id
    else
      arr << @value
    end
    @@nodes[@left].preorder(arr, bool) if @left
    @@nodes[@right].preorder(arr, bool) if @right
    return arr
  end
  
  def inorder(arr, bool = true)
    @@nodes[@left].inorder(arr, bool) if @left
    if bool
      arr << @id
    else
      arr << @value
    end
    @@nodes[@right].inorder(arr, bool) if @right
    return arr
  end
  
  def postorder(arr, bool = true)
    @@nodes[@left].postorder(arr, bool) if @left
    @@nodes[@right].postorder(arr, bool) if @right
    if bool
      arr << @id
    else
      arr << @value
    end
    return arr
  end
  
  def inspect
    return [@id, @value, @left, @right]
  end
  
  def to_s(bool = true)
    @id
  end
  
  def to_exp
    "node #{@value}: parent = #{@parent.to_i}, sibling = #{@sibling.to_i}, degree = #{degree}, depth = #{depth}, height = #{height}, #{type}"
  end
end
def f(preorder, inorder)
  root = preorder[0]
  idx = inorder.index(root)
  root.set_left(f(preorder & inorder[0...idx], inorder[0...idx])) if idx > 0
  root.set_right(f(preorder & inorder[idx + 1..-1], inorder[idx + 1 ..-1])) if idx < inorder.length - 1
  return root.to_i
end
def main
  count = 1
  arr = []
  gets.to_i.times do
    get = gets.split(" ")
    if get[0] == "insert"
      arr << Graph.new(count, nil, nil, get[1].to_i)
      arr.first.insert(arr.last)
      count += 1
    else
      arr.first.print
    end
  end
end
main