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

class Node(var key:Int, var left:Node = null, var right:Node = null) { }

object Main {
  def scan(list:List[Node]):Unit = {
    list match {
      case Nil => ()
      case hd::tl => {
        print(" "+hd.key)
        val hd2 = if(hd.right!=null) hd.right::tl else tl
        val hd3 =if(hd.left!=null) hd.left::hd2 else hd2
        scan(hd3)
      }
    }
  }

  def insert(node:Node, keyNode:Node):Unit =
    if(node.key > keyNode.key) {
      if(node.left == null) node.left = keyNode
      else insert(node.left, keyNode)
    } else {
      if(node.right == null) node.right = keyNode
      else insert(node.right, keyNode)
    }


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

    while(flg) {
      while(curr != null) {
        stack = curr::stack
        curr = curr.left
      }
      if(curr == null && stack != Nil) {
        val item = stack.head
        stack = stack.tail
        print(" "+item.key)
        curr = item.right
      } else {
        flg = false
      }
    }
  }

  def preOrder(tree:Node):Unit =
    if(tree == null) return
    else  scan(tree::Nil)

  def main(args:Array[String]) = {
    val n = readInt
    val tree = new Node(-1)

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