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

object Main {
  class Node(val key:Int, var left:Option[Node] = None, var right:Option[Node] = None) { }

  def insert(tree:Option[Node], key:Option[Node]):Option[Node] = {
    val keyNode = key.get

    def getNodeToInsert(node:Option[Node], prevNode:Option[Node]):Option[Node] = node match {
      case None => prevNode
      case Some(x) =>
        if(x.key > keyNode.key) getNodeToInsert(x.left, Some(x))
        else getNodeToInsert(x.right, Some(x))
    }
    val targetNode = getNodeToInsert(tree,tree)

    targetNode match {
      case None => key
      case Some(x) =>
        if(keyNode.key < x.key) { x.left = Some(keyNode); tree}
        else { x.right = Some(keyNode); tree}
    }
  }

  def inOrder(tree:Option[Node]):Unit = tree match {
    case None => return
    case Some(x) => {
      inOrder(x.left)
      print(" "+x.key)
      inOrder(x.right)
    }
  }

  def preOrder(tree:Option[Node]):Unit = tree match {
    case None => return
    case Some(x) => {
      print(" "+x.key)
      preOrder(x.left)
      preOrder(x.right)
    }
  }

  def main(args:Array[String]) = {
    val n = readInt
    var tree:Option[Node] = None

    for(i<-0 until n) {
      val s = readLine.split(" ")
      s(0) match {
        case "insert" =>
          tree = insert(tree,Some(new Node(s(1).toInt)))
        case _ => {
          inOrder(tree);println
          preOrder(tree);println
        }
      }
    }
  }
}