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

object Main {
  val tree = new Array[(Int,Int,Int)](500001)

  def insert(i:Int, j:Int):Unit =
    if(tree(i)._1 > tree(j)._1) {
      if(tree(i)._2 == -1) tree(i) = (tree(i)._1, j, tree(i)._3)
      else insert(tree(i)._2, j)
    } else {
      if(tree(i)._3 == -1) tree(i) = (tree(i)._1, tree(i)._2, j)
      else insert(tree(i)._3, j)
    }

  def inOrder(i:Int):Unit =
    if(i == -1) return
    else {
      inOrder(tree(i)._2)
      print(" "+tree(i)._1)
      inOrder(tree(i)._3)
    }

  def preOrder(i:Int):Unit =
    if(i == -1) return
    else {
      print(" "+tree(i)._1)
      preOrder(tree(i)._2)
      preOrder(tree(i)._3)
    }

  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) = (s(1).toInt,-1,-1)
          if(j!=0) insert(0, j)
          j+=1
        }
        case _ => {
          inOrder(0);println
          preOrder(0);println
        }
      }
    }
  }
}