import java.lang.Exception

var nodeList = arrayListOf<Treee>()

fun main(args: Array<String>) {

    val count = readLine()!!.toLong()
    for (i in 1..count) {
        val order = readLine()!!
        when {
            order.contains("insert") -> {
                insert(order.split(" ")[1].toInt())
            }
            order.contains("print") -> {
                printByInorder(nodeList[0])
                println()
                printByPreorder(nodeList[0])
                println()
            }
        }
    }
}

fun insert(addedKey: Int) {
    val addedNode = Treee(nodeList.count(), key = addedKey)

    if (nodeList.count() == 0) {
        nodeList.add(addedNode)
        return
    }

    // ルートノーのから開始
    var x = nodeList[0]
    while (true) {
        if (x.key < addedKey) {

            // 右に配置
            if (x.right == null) {
                x.right = addedNode
                break

            } else {
                x = x.right!!
            }
        } else if (x.key > addedKey) {

            // 左に配置
            if (x.left == null) {
                x.left = addedNode
                break;

            } else {
                x = x.left!!
            }

        } else {
            throw Exception("key is duplicated!!!")
        }
    }

    nodeList.add(addedNode)
}

fun printByPreorder(node: Treee) {

    print(" ${node.key}")

    if (node.left != null) {
        printByPreorder(node.left!!)
    }

    if (node.right != null) {
        printByPreorder(node.right!!)
    }
}


fun printByInorder(node: Treee) {

    if (node.left != null) {
        printByInorder(node.left!!)
    }

    print(" ${node.key}")

    if (node.right != null) {
        printByInorder(node.right!!)
    }
}

data class Treee(
    var id: Int,
    var parent: Int = -1,
    var left: Treee? = null,
    var right: Treee? = null,
    var key: Int
)
