import scala.collection.mutable.Stack
import scala.io.StdIn.{readInt, readLine}

object Main extends App {

  val bst = new Bst()
  val n = readInt
  for (_ <- 0 until n) {
    val arr = readLine.split(" ")
    val cmd = arr(0)
    cmd match {
      case "insert" => bst.insert(arr(1).toInt)
      case "print" => bst.printTree()
    }
  }

  class Node(val value: Int) {
    var left: Node = null
    var right: Node = null
    var visited: Boolean = false
  }

  class Bst {
    var size = 0
    var root: Node = null
    def insert(value: Int): Unit = {
      size += 1
      if (root == null) {
        root = new Node(value)
        return
      }
      var prev: Node = null
      var cur = root
      while (cur != null) {
        prev = cur
        if (cur.value > value) {
          cur = cur.left
          if (cur == null) prev.left = new Node(value)
        } else {
          cur = cur.right
          if (cur == null) prev.right = new Node(value)
        }
      }
    }

    def printTree(): Unit = {
      printInOrder()
      printPreOrder()
    }

    def printInOrder(): Unit = {
      val stack = new Stack[Node]
      stack.push(root)
      while (!stack.isEmpty) {
        var node = stack.top
        while (node.left != null && !node.left.visited) {
          stack.push(node.left)
          node = node.left
        }
        node = stack.pop
        if (!node.visited) {
          print(s" ${node.value}")
          node.visited =true
        }
        if (node.right != null && !node.right.visited) {
          stack.push(node.right)
        }
      }
      println()
    }

    def printPreOrder(): Unit = {
      val stack = new Stack[Node]
      stack.push(root)
      while (!stack.isEmpty) {
        val node = stack.pop
        if (node != null) {
          print(s" ${node.value}")
          node.visited = false
          stack.push(node.right)
          stack.push(node.left)
        }
      }
      println()
    }

  }
}

