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

object Main {
  val tree0 = new Array[Int](500001)
  val tree1 = new Array[Int](500001)
  val tree2 = new Array[Int](500001)
  val out:BufferedWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512)
  var count = 0

  def insert(i:Int, j:Int):Unit =
    if(tree0(i) > tree0(j)) {
      if(tree1(i) == -1) tree1(i) = j
      else insert(tree1(i), j)
    } else {
      if(tree2(i) == -1) tree2(i) = j
      else insert(tree2(i), j)
    }

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

    while(flg) {
      while(curr != -1) {
        stack = curr::stack
        curr = tree1(curr)
      }
      if(curr == -1 && stack != Nil) {
        val item = stack.head
        stack = stack.tail
        out.write(" ")
        out.write(tree0(item).toString)
        if(count<100) count += 1
        else {
          out.flush
          count = 0
        }
        curr = tree2(item)
      } else {
        flg = false
      }
    }
  }

  def scan(list:List[Int]):Unit = {
    list match {
      case Nil => ()
      case hd::tl => {
        out.write(" ")
        out.write(tree0(hd).toString)
        if(count<100) count += 1
        else {
          out.flush
          count = 0
        }
        val hd2 =
          if(tree2(hd) != -1 && tree1(hd) != -1) tree1(hd)::tree2(hd)::tl
          else if(tree2(hd) != -1 && tree1(hd) == -1) tree2(hd)::tl
          else if(tree2(hd) == -1 && tree1(hd) != -1) tree1(hd)::tl
          else tl
        scan(hd2)
      }
    }
  }

  def preOrder(i:Int):Unit =
    if(i == -1) return
    else scan(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" => {
          tree0(j) = s(1).toInt
          tree1(j) = -1
          tree2(j) = -1
          if(j!=0) insert(0, j)
          j+=1
        }
        case _ => {
          inOrder()
          out.write("\n")
          out.flush()
          preOrder(0)
          out.write("\n")
          out.flush()
        }
      }
    }
  }
}