fun main(args: Array<String>) {
    val binaryTree = BinaryTree<Int>()
    repeat(readLine()?.toInt() ?: 0) {
        val input = readLine()?.split(" ".toRegex()) ?: return@repeat
        when (input[0]) {
            "insert" -> binaryTree.insert(input[1].toInt())
            "print" -> binaryTree.printTree()
        }
    }
}

class BinaryTree<T: Comparable<T>> {
    private var root: Node? = null

    fun insert(key: T) {
        val newNode = Node(key)
        var x = root
        var y = x?.parent
        while (x != null) {
            y = x
            x = if (key < x.key) {
                x.leftChild
            } else {
                x.rightChild
            }
        }
        newNode.parent = y
        when {
            y == null -> root = newNode
            key < y.key -> y.leftChild = newNode
            else -> y.rightChild = newNode
        }
    }

    fun printTree() {
        println(inorderTreeWalk())
        println(preorderTreeWalk())
    }

    private fun inorderTreeWalk(): String {
        val root = this.root ?: return ""
        return inorderTreeWalk(root)
    }

    private fun inorderTreeWalk(node: Node): String {
        val resultBuilder = StringBuilder()
        if (node.leftChild != null) {
            resultBuilder.append(inorderTreeWalk(node.leftChild!!))
        }
        resultBuilder.append(" ")
        resultBuilder.append(node.key)
        if (node.rightChild != null) {
            resultBuilder.append(inorderTreeWalk(node.rightChild!!))
        }
        return resultBuilder.toString()
    }

    private fun preorderTreeWalk(): String {
        val root = this.root ?: return ""
        return preorderTreeWalk(root)
    }

    private fun preorderTreeWalk(node: Node): String {
        val resultBuilder = StringBuilder()
        resultBuilder.append(" ")
        resultBuilder.append(node.key)
        if (node.leftChild != null) {
            resultBuilder.append(preorderTreeWalk(node.leftChild!!))
        }
        if (node.rightChild != null) {
            resultBuilder.append(preorderTreeWalk(node.rightChild!!))
        }
        return resultBuilder.toString()
    }

    inner class Node(val key: T) {
        var parent: Node? = null
        var leftChild: Node? = null
        var rightChild: Node? = null
    }
}
