object Main extends App {
  val n: Int = io.StdIn.readInt()
  val bt: BTree = Empty
  
  (0 until n).foldLeft[BTree](bt){(t, _) =>
    val ops: Array[String] = io.StdIn.readLine().split(" ")
    if (ops.length == 1) {t.show; t}
    else t.insert(ops(1).toInt)
  }
}

sealed trait BTree {
  def insert(x: Int): BTree
  def preorder: List[Int]
  def inorder: List[Int]
  def show: Unit = {
    println(" " + this.inorder.mkString(" "))
    println(" " + this.preorder.mkString(" "))
  }
}
object Empty extends BTree {
  def insert(x: Int): BTree = new Node(x, Empty, Empty)
  def preorder: List[Int] = Nil
  def inorder: List[Int] = Nil
}
class Node(v: Int, l: BTree, r: BTree) extends BTree {
  def insert(x: Int): BTree =
    if (x < v) new Node(v, l.insert(x), r)
    else new Node(v, l, r.insert(x))
  def preorder: List[Int] = v :: (l.preorder ::: r.preorder)
  def inorder: List[Int]  = l.inorder ::: (v :: r.inorder)
}
