import scala.io.StdIn.{readInt, readLine}

object Main {
  val tree = Array.ofDim[Int](500001,3)

  def insert(i:Int, j:Int):Unit =
    if(tree(i)(0) > tree(j)(0)) {
      if(tree(i)(1) == -1) tree(i)(1) = j
      else insert(tree(i)(1), j)
    } else {
      if(tree(i)(2) == -1) tree(i)(2) = j
      else insert(tree(i)(2), j)
    }

  def inOrder():Unit = {
    var stack:List[Array[Int]] = Nil
    var curr = 0
    var flg = true

    while(flg) {
      while(curr != -1) {
        stack = tree(curr)::stack
        curr = tree(curr)(1)
      }
      if(curr == -1 && stack != Nil) {
        val item = stack.head
        stack = stack.tail
        print(" "+item(0))
        curr = item(2)
      } else {
        flg = false
      }
    }
  }

  def scan(list:List[Array[Int]]):Unit = {
    list match {
      case Nil => ()
      case hd::tl => {
        print(" "+hd(0))
        val hd2 = if(hd(2) != -1) tree(hd(2))::tl else tl
        val hd3 = if(hd(1) != -1) tree(hd(1))::hd2 else hd2
        scan(hd3)
      }
    }
  }

  def preOrder(i:Int):Unit =
    if(i == -1) return
    else scan(tree(i)::Nil)

  def main(args:Array[String]) = {
    val n = readInt
    var j = 0

    for(i<-0 until n) {
      val s = readLine.split(" ")
      s(0) match {
        case "insert" => {
          tree(j) = Array(s(1).toInt,-1,-1)
          if(j!=0) insert(0, j)
          j+=1
        }
        case _ => {
          inOrder();println
          preOrder(0);println
        }
      }
    }
  }
}