

sealed class Treap<out V, out H>{
    abstract fun inOrderWalk(separator: String = " ", prefix: String = "", suffix: String = ""): String
    abstract fun preOrderWalk(separator: String = " ", prefix: String = "", suffix: String = ""): String
    data class Node<V: Comparable<V>, H: Comparable<H>> constructor (val value:V, val heap:H, val left: Treap<V, H> = Nil, val right: Treap<V, H> = Nil): Treap<V, H>() {
        override fun preOrderWalk(separator: String, prefix: String, suffix: String): String {
            return "$prefix$value${left.preOrderWalk(separator, separator,"")}${right.preOrderWalk(separator,separator, "")}$suffix"
        }

        override fun inOrderWalk(separator: String, prefix: String, suffix: String): String {
            return "$prefix${left.inOrderWalk(separator, "", separator)}$value${right.inOrderWalk(separator, separator, "")}$suffix"
        }

    }

    object Nil: Treap<Nothing, Nothing>() {
        override fun inOrderWalk(separator: String, prefix: String, suffix: String): String {
            return ""
        }

        override fun preOrderWalk(separator: String, prefix: String, suffix: String): String {
            return ""
        }
    }

    companion object {
        operator fun <V: Comparable<V>, H: Comparable<H>>invoke(): Treap<V, H> = Nil
        operator fun <V: Comparable<V>, H: Comparable<H>>invoke(value: V, heap: H): Treap<V, H> {
            return Node(value, heap)
        }
        fun <V: Comparable<V>, H: Comparable<H>> insert(treap: Treap<V, H>, value: V, heap: H): Node<V, H> {
            return when(treap){
                is Nil -> Node(value, heap)
                is Node<V, H> -> if (treap.value > value){
                    val newLeft = insert(treap.left, value, heap)
                    if (heap > treap.heap) Node(value, heap, newLeft.left, Node(treap.value, treap.heap, newLeft.right, treap.right))
                    else Node(treap.value, treap.heap, newLeft, treap.right)
                }else {
                    val newRight = insert(treap.right, value, heap)
                    if (heap > treap.heap) Node(value, heap, Node(treap.value, treap.heap, treap.left, newRight.left), newRight.right)
                    else Node(treap.value, treap.heap, treap.left, newRight)
                }
            }
        }
        fun <V: Comparable<V>, H: Comparable<H>> deleteNode(treap: Treap<V, H>, value:V): Treap<V, H> {
            return when(treap){
                is Nil -> treap
                is Node<V, H> ->
                    when{
                        treap.value < value -> Node(treap.value, treap.heap, treap.left, deleteNode(treap.right, value))
                        treap.value > value -> Node(treap.value, treap.heap, deleteNode(treap.left, value), treap.right)
                        else -> deleteThis(treap)
                    }
            }
        }
        private fun <V: Comparable<V>, H: Comparable<H>> deleteThis(treap: Treap<V, H>): Treap<V, H> {
            return when(treap) {
                is Nil -> treap
                is Node<V, H> -> {
                    when{
                        treap.left is Node<V, H> && treap.right is Node<V, H> ->
                            if (treap.left.heap > treap.right.heap) Node(treap.left.value, treap.left.heap, treap.left.left, deleteThis(Node(treap.value, treap.heap, treap.left.right, treap.right)))
                            else Node(treap.right.value, treap.right.heap, deleteThis(Node(treap.value, treap.heap, treap.left, treap.right.left)), treap.right.right)
                        treap.left is Nil -> treap.right
                        else -> treap.left
                    }
                }
            }
        }
    }
}
fun <V: Comparable<V>> Treap<V, *>.find(value:V): Boolean {
    return when(this){
        is Treap.Nil -> false
        is Treap.Node<V, *> -> when{
            this.value < value -> right.find(value)
            this.value > value -> left.find(value)
            else -> true
        }
    }
}
fun <V: Comparable<V>, H: Comparable<H>> Treap<V, H>.insert(value: V, heap: H): Treap<V, H> {
    return Treap.insert(this, value, heap)
}
fun <V: Comparable<V>, H: Comparable<H>> Treap<V, H>.delete(value: V): Treap<V, H> {
    return Treap.deleteNode(this, value)
}

fun main(args:Array<String>): Unit {
    var treap = Treap<Int, Int>()
    repeat(readLine()!!.toInt()){
        val order = readLine()!!.trim().split(' ')
        when(order.first()){
            "insert" -> treap = treap.insert(order[1].toInt(), order[2].toInt())
            "delete" -> treap = treap.delete(order[1].toInt())
            "find" -> println(if (treap.find(order[1].toInt())) "yes" else "no")
            else -> {
                println(treap.inOrderWalk(" ", " "))
                println(treap.preOrderWalk(" ", " "))
            }
        }
    }
}
