Problem:

Treap

  A binary search tree can be unbalanced depending on features of data. For example, if we insert $n$ elements into a binary search tree in ascending order, the tree become a list, leading to long search times. One of strategies is to randomly shuffle the elements to be inserted. However, we should consider to maintain the balanced binary tree where different operations can be performed one by one depending on requirement.

  We can maintain the balanced binary search tree by assigning a priority randomly selected to each node and by ordering nodes based on the following properties. Here, we assume that all priorities are distinct and also that all keys are distinct.

  
binary-search-tree property. If $v$ is a left child of $u$, then $v.key right child of $u$, then $u.key heap property. If $v$ is a child of $u$, then $v.priority 

  Insert

  To insert a new element into a Treap, first of all, insert a node which a randomly selected priority value is assigned in the same way for ordinal binary search tree. For example, the following figure shows the Treap after a node with key = 6 and priority = 90 is inserted.

It is clear that this Treap violates the heap property, so we need to modify the structure of the tree by rotate operations. The rotate operation is to change parent-child relation while maintaing the binary-search-tree property.

  The rotate operations can be implemented as follows.

  

    

rightRotate(Node t)
    Node s = t.left
    t.left = s.right
    s.right = t
    return s // the new root of subtree

leftRotate(Node t)
    Node s = t.right
    t.right = s.left
    s.left = t
    return s // the new root of subtree

  The following figure shows processes of the rotate operations after the insert operation to maintain the properties.

  The insert operation with rotate operations can be implemented as follows.

insert(Node t, int key, int priority)            // search the corresponding place recursively
    if t == NIL
        return Node(key, priority)               // create a new node when you reach a leaf
    if key == t.key
        return t                                 // ignore duplicated keys

    if key Delete

  To delete a node from the Treap, first of all, the target node should be moved until it becomes a leaf by rotate operations. Then, you can remove the node (the leaf). These processes can be implemented as follows.

delete(Node t, int key)                        // seach the target recursively
    if t == NIL
        return NIL
    if key  t.key
        t.right = delete(t.right, key)
    else
        return _delete(t, key)
    return t

_delete(Node t, int key)                       // if t is the target node
    if t.left == NIL && t.right == NIL         // if t is a leaf
        return NIL
    else if t.left == NIL                      // if t has only the right child, then perform left rotate
        t = leftRotate(t)
    else if t.right == NIL                     // if t has only the left child, then perform right rotate
        t = rightRotate(t)
    else                                       // if t has both the left and right child
        if t.left.priority > t.right.priority  // pull up the child with higher priority
            t = rightRotate(t)
        else
            t = leftRotate(t)
    return delete(t, key)

  Write a program which performs the following operations to a Treap $T$ based on the above described algorithm.

insert ($k$, $p$): Insert a node containing $k$ as key and $p$ as priority to $T$.

find ($k$): Report whether $T$ has a node containing $k$.

delete ($k$): Delete a node containing $k$.

print(): Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.

Input

    

In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k \; p$, find $k$, delete $k$ or print are given.

Output

For each find($k$) operation, print "yes" if $T$ has a node containing $k$, "no" if not.

  In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.

Constraints

The number of operations $ \leq 200,000$

$0 \leq k, p  \leq 2,000,000,000$

The height of the binary tree does not exceed 50 if you employ the above algorithm

The keys in the binary search tree are all different.

The priorities in the binary search tree are all different.

The size of output $\leq 10$ MB

Sample Input 1

16
insert 35 99
insert 3 80
insert 1 53
insert 14 25
insert 80 76
insert 42 3
insert 86 47
insert 21 12
insert 7 10
insert 6 90
print
find 21
find 22
delete 35
delete 99
print

Sample Output 1

 1 3 6 7 14 21 35 42 80 86
 35 6 3 1 14 7 21 80 42 86
yes
no
 1 3 6 7 14 21 42 80 86
 6 3 1 80 14 7 21 42 86

Reference

  
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

  
Randomized Search Trees, R. Seidel, C.R. Aragon.



Sample input:
16
insert 35 99
insert 3 80
insert 1 53
insert 14 25
insert 80 76
insert 42 3
insert 86 47
insert 21 12
insert 7 10
insert 6 90
print
find 21
find 22
delete 35
delete 99
print


Sample output:
 1 3 6 7 14 21 35 42 80 86
 35 6 3 1 14 7 21 80 42 86
yes
no
 1 3 6 7 14 21 42 80 86
 6 3 1 80 14 7 21 42 86

Submission status: Accepted

Solution code:
class Treap:
    class TreapNode:
        def __init__(self, key, priority, leftchild=None, rightchild=None):
            self.key = key
            self.priority = priority
            self.leftchild = leftchild
            self.rightchild = rightchild

        def __repr__(self):
            return f'({self.key}, {self.priority})'

    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def rotateR(self, t):
        s = t.leftchild
        t.leftchild = s.rightchild
        s.rightchild = t
        return s

    def rotateL(self, t):
        s = t.rightchild
        t.rightchild = s.leftchild
        s.leftchild = t
        return s

    def _insert(self, t, key, priority):
        if t is None:
            return self.TreapNode(key, priority)
        if key == t.key:
            return t
        if key < t.key:
            t.leftchild = self._insert(t.leftchild, key, priority)
            if t.priority < t.leftchild.priority:
                t = self.rotateR(t)
        else:
            t.rightchild = self._insert(t.rightchild, key, priority)
            if t.priority < t.rightchild.priority:
                t = self.rotateL(t)
        return t

    def insert(self, key, priority):
        self.root = self._insert(self.root, key, priority)

    def _delete_rotate(self, t, key):
        if t.leftchild is None and t.rightchild is None:
            return None
        elif t.leftchild is None:
            t = self.rotateL(t)
        elif t.rightchild is None:
            t = self.rotateR(t)
        else:
            if t.leftchild.priority > t.rightchild.priority:
                t = self.rotateR(t)
            else:
                t = self.rotateL(t)
        return self._delete(t, key)

    def _delete(self, t, key):
        if t is None:
            return None
        if key < t.key:
            t.leftchild = self._delete(t.leftchild, key)
        elif key > t.key:
            t.rightchild = self._delete(t.rightchild, key)
        else:
            return self._delete_rotate(t, key)
        return t

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _find(self, t, key):
        if t is None:
            return False
        elif key < t.key:
            return self._find(t.leftchild, key)
        elif key > t.key:
            return self._find(t.rightchild, key)
        else:
            return True

    def find(self, key):
        return self._find(self.root, key)

    def _walk(self, t):
        if t is None:
            return
        self.preorder.append(t.key)
        self._walk(t.leftchild)
        self.inorder.append(t.key)
        self._walk(t.rightchild)

    def walk(self):
        self.inorder.clear()
        self.preorder.clear()
        self._walk(self.root)

    def print(self):
        self.walk()
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))


T = Treap()
N = int(input())
for _ in range(N):
    s = input().split()
    s[1:] = map(int, s[1:])
    if s[0] == 'insert':
        T.insert(s[1], s[2])
    if s[0] == 'find':
        print('yes' if T.find(s[1]) else 'no')
    if s[0] == 'delete':
        T.delete(s[1])
    if s[0] == 'print':
        T.print()

Submission status: Accepted

Solution code:
import random
from collections import deque


class TreapNode():
    """節クラス: valは節の値, priorityは節の優先度を表す
    parent/left/rightはそれぞれ親/左側の子/右側の子へのポインタを表す
    """
    def __init__(self, val, priority):
        self.val = val
        self.priority = priority # random.random()
        self.parent = None
        self.right = None
        self.left = None


class Treap():
    """SSet(Sorted Set)をサポートする"""
    def __init__(self):
        self.root = None

    def search(self, val: int) -> bool:
        """二分木に値valを持つ節が存在するかどうか判定する
        valと一致する節が存在する場合はTrue、存在しない場合はFalseを返す
        """
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False 

    def insert(self, val: int, priority):
        """二分木に値valを持つ節が存在しない場合、追加する"""
        if self.root is None:
            self.root = TreapNode(val, priority)
            return

        ptr = self.root 
        while True:
            if val == ptr.val:
                return
            elif val < ptr.val:
                if ptr.left is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.left = TreapNode(val, priority)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if ptr.right is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.right = TreapNode(val, priority)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right
       
        while (ptr.parent is not None) and (ptr.parent.priority < ptr.priority):
            if ptr.parent.right == ptr:
                self.rotate_left(ptr.parent)
            else:
                self.rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
          
          
    def delete(self, val: int):
        """二分木から値valを持つ節を削除する"""        
        ptr = self.root             
        while True: 
            if ptr is None:
                return
            elif val == ptr.val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
       
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self.rotate_left(ptr)
            elif ptr.right is None:
                self.rotate_right(ptr)
            elif ptr.left.priority > ptr.right.priority:
                self.rotate_right(ptr)
            else:
                self.rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent
       
        if ptr.parent.left == ptr:
            ptr.parent.left = None
        else:
            ptr.parent.right = None         
   
    def rotate_left(self, ptr):
        """木を左回転する"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None
     
    def rotate_right(self, ptr):
        """木を右回転する"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def preorder_tree_walk(self):
        """先行順巡回(preorder tree walk)"""
        res = []
        q = deque([])
        ptr = self.root
        while True:
            if ptr is not None:
                q.append(ptr) 
                res.append(ptr.val)
                ptr = ptr.left
            elif q: 
                ptr = q.pop() 
                ptr = ptr.right
            else:
                return res
 
    def inorder_tree_walk(self):
        """中間順巡回(inorder tree walk)"""
        res = []
        q = deque([])
        ptr = self.root
        while True:
            if ptr is not None:
                q.append(ptr) 
                ptr = ptr.left
            elif q: 
                ptr = q.pop() 
                res.append(ptr.val)
                ptr = ptr.right
            else:
                return res
 
    def postorder_tree_walk(self):
        """後行順巡回(postorder tree walk)"""
        res = []
        q = deque([self.root])
        ptr = self.root
        while q:
            ptr = q.pop()
            res.append(ptr.val)
            if ptr.left is not None:
                q.append(ptr.left)
            if ptr.right is not None:
                q.append(ptr.right)
        return reversed(res)

n = int(input())
info = [list(input().split()) for i in range(n)]
tp = Treap()

for i in range(n):
    if info[i][0] == "insert":
        tp.insert(int(info[i][1]), int(info[i][2]))
    elif info[i][0] == "find":
        if tp.search(int(info[i][1])):
            print("yes")
        else:
            print("no")
    elif info[i][0] == "delete":
        tp.delete(int(info[i][1]))
    else:
        print(" ", end="")
        print(*tp.inorder_tree_walk())
        print(" ", end="")
        print(*tp.preorder_tree_walk())

Submission status: Accepted

Solution code:

class Node:
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.parent = None
        self.left = None
        self.right = None


def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s


def leftRotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s


def insert(t, key, priority):
    if t is None:
        return Node(key, priority)
    if key == t.key:
        return t

    if key < t.key:
        t.left = insert(t.left, key, priority)
        if t.priority < t.left.priority:
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, priority)
        if t.priority < t.right.priority:
            t = leftRotate(t)

    return t


def delete(t, key):
    if t is None:
        return None
    if key < t.key:
        t.left = delete(t.left, key)
    elif key > t.key:
        t.right = delete(t.right, key)
    else:
        return _delete(t, key)
    return t


def _delete(t, key):
    if t.left is None and t.right is None:
        return None
    elif t.left is None:
        t = leftRotate(t)
    elif t.right is None:
        t = rightRotate(t)
    else:
        if t.left.priority > t.right.priority:
            t = rightRotate(t)
        else:
            t = leftRotate(t)
    return delete(t, key)


def find(t, key):
    if key == t.key:
        return t

    elif key < t.key:
        if t.left is not None:
            ret = find(t.left, key)
            if ret is not None:
                return ret
    else:
        if t.right is not None:
            ret = find(t.right, key)
            if ret is not None:
                return ret

    return None


def preorder(t, ret):
    ret.append(t.key)

    if t.left is not None:
        preorder(t.left, ret)

    if t.right is not None:
        preorder(t.right, ret)


def inorder(t, ret):
    if t.left is not None:
        inorder(t.left, ret)

    ret.append(t.key)

    if t.right is not None:
        inorder(t.right, ret)


def main():
    m = int(input())
    Treap = None
    for i in range(m):
        cmd, *v = input().split()
        if cmd == "print":
            print(" ", end="")
            inans = []
            inorder(Treap, inans)
            print(*inans)
            print(" ", end="")
            preans = []
            preorder(Treap, preans)
            print(*preans)
        elif cmd == "insert":
            k = int(v[0])
            p = int(v[1])
            Treap = insert(Treap, k, p)
        elif cmd == "find":
            z = int(v[0])
            if find(Treap, z) == None:
                print("no")
            else:
                print("yes")
        else:
            z = int(v[0])
            Treap = delete(Treap, z)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import Optional, List


class Node():
    def __init__(self, key: int, priority: int) -> None:
        self.key = key
        self.priority = priority
        self.parent: Optional[Node] = None
        self.left: Optional[Node] = None
        self.right: Optional[Node] = None

    def prewalk(self) -> List[int]:
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret

    def inwalk(self) -> List[int]:
        ret: List[int] = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret


class Tree():
    def __init__(self) -> None:
        self.root: Optional[Node] = None

    def insert(self, node: Optional[Node], key: int, priority: int) -> Node:
        if self.root is None:
            self.root = Node(key, priority)
            return self.root
        if node is None:
            return Node(key, priority)
        if key == node.key:
            # Duplicated key case (No insertion).
            return node

        if key < node.key:
            node.left = self.insert(node.left, key, priority)
            if node.priority < node.left.priority:
                node = self._right_rotate(node)
        else:
            node.right = self.insert(node.right, key, priority)
            if node.priority < node.right.priority:
                node = self._left_rotate(node)

        return node

    def _right_rotate(self, t: Node) -> Node:
        assert t.left is not None
        s: Node = t.left
        t.left = s.right
        s.right = t
        return s  # The new root of the subtree.

    def _left_rotate(self, t: Node) -> Node:
        assert t.right is not None
        s: Node = t.right
        t.right = s.left
        s.left = t
        return s  # The new root of the subtree.

    def find(self, key: int) -> Optional[Node]:
        x = self.root
        while x and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        return x

    def delete(self, node: Optional[Node], key: int) -> Optional[Node]:
        if node is None:
            return node
        if key < node.key:
            node.left = self.delete(node.left, key)
        elif key > node.key:
            node.right = self.delete(node.right, key)
        else:
            return self._delete(node, key)
        return node

    def _delete(self, node: Node, key: int) -> Optional[Node]:
        if (node.left is None) and (node.right is None):
            return None
        elif node.left is None:
            node = self._left_rotate(node)
        elif node.right is None:
            node = self._right_rotate(node)
        else:
            assert node.left is not None  # Though this is not needed in principle...
            if node.left.priority > node.right.priority:
                node = self._right_rotate(node)
            else:
                node = self._left_rotate(node)
        return self.delete(node, key)

    def _successor(self, x: Node) -> Node:
        assert x is not None
        if x.right:
            return self._minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        assert y is not None
        return y

    def _minimum(self, x: Node) -> Node:
        while x.left:
            x = x.left
        return x

    def print(self) -> None:
        assert self.root is not None
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))


if __name__ == "__main__":
    tree = Tree()
    node_num = int(input())
    for _ in range(node_num):
        command, *value = input().split()
        if "insert" == command:
            tree.root = tree.insert(tree.root, int(value[0]), int(value[1]))
        elif "find" == command:
            print('yes' if tree.find(int(value[0])) else 'no')
        elif "delete" == command:
            tree.root = tree.delete(tree.root, int(value[0]))
        elif "print" == command:
            tree.print()
        else:
            pass

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.parent = None
        self.left = None
        self.right = None

# 根
parent_node = None    
    
# カウンター
counter = 0
        
def getRoot(u):
    while u.parent != None:
        u = u.parent
    return u


def printPreorder(u):
    if u == None:
        return
    print(" ", u.key, sep="", end="")
    printPreorder(u.left)
    printPreorder(u.right)

    
def printInorder(u):
    if u == None:
        return
    printInorder(u.left)
    print(" ", u.key, sep="", end="")
    printInorder(u.right)

    
def find(u, num):
    while u != None and u.key != num:
        if num < u.key:
            u = u.left
        else:
            u = u.right
    if u != None:
        print("yes")
    else:
        print("no")


def rightRotate(u):
    # print("right")
    s = u.left
    u.left = s.right
    # 親の更新
    if u.left != None:
        u.left.parent = u
    
    s.right = u 
    # 親の更新
    s.parent = u.parent
    u.parent = s
    return s

def leftRotate(u):
    # print("left")
    s = u.right
    u.right = s.left
    # 親の更新
    if u.right != None:
        u.right.parent = u
    
    s.left = u
    # 親の更新
    s.parent = u.parent
    u.parent = s
    return s

        
def insert(u, key, priority):
    # print("insert 1")
    global parent_node
    global counter
    if u == None:
        s = Nodes[counter]
        # カウンターの増加
        counter += 1
        s.key = key
        s.priority = priority
        # 根のノードの更新
        if parent_node == None:
            parent_node = s
        return s
    
    if key == u.key:
        return u
    
    if key < u.key:
        u.left = insert(u.left, key, priority)
        # 親の更新
        u.left.parent = u
        if u.priority < u.left.priority:
            u = rightRotate(u)
    else:
        u.right = insert(u.right, key, priority)
        # 親の更新
        u.right.parent = u
        if u.priority < u.right.priority:
            u = leftRotate(u)
    
    return u
    

def delete(u, key):
    # print("delete")
    if u == None:
        return None
    if key < u.key:
        u.left = delete(u.left, key)
    elif key > u.key:
        u.right = delete(u.right, key)
    else:
        return _delete(u, key)
    return u


def _delete(u, key):
    # print("_delete")
    if u.left == None and u.right == None:
        return None
    elif u.left == None:
        u = leftRotate(u)
    elif u.right == None:
        u = rightRotate(u)
    else:
        if u.left.priority > u.right.priority:
            u = rightRotate(u)
        else:
            u = leftRotate(u)
    return delete(u, key)
    
    
n = int(input())

# メモリの確保
Nodes = []
for i in range(n):
    tmp_node = Node(0, 0)
    Nodes.append(tmp_node)



for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        key = int(cmd[1])
        priority = int(cmd[2])
        insert(parent_node, key, priority)
        # print("test in")
        # 根が変わる場合を考慮する。
        parent_node = getRoot(parent_node)
        # print("test out")
    # プリント
    elif cmd[0] == 'print':
        printInorder(parent_node)
        print("")
        printPreorder(parent_node)
        print("")
    # サーチ
    elif cmd[0] == 'find':
        key = int(cmd[1])
        find(parent_node, key)
    # 削除
    else:
        key = int(cmd[1])
        
        # 根が変わる場合を考慮する。
        if parent_node.key != key:
            delete(parent_node, key)
            parent_node = getRoot(parent_node)
        elif parent_node.left != None:
            tmp_node = parent_node.left
            delete(parent_node, key)
            parent_node = getRoot(tmp_node)
        elif parent_node.right != None:
            tmp_node = parent_node.right
            delete(parent_node, key)
            parent_node = getRoot(tmp_node)
        else:
            delete(parent_node, key)
            parent_node = None

Submission status: Accepted

Solution code:
NIL = -1


class Node():
    __slots__ = ["key", "parent", "left", "right"]

    def __init__(self, key=NIL):
        self.key = key
        self.parent = NIL
        self.left = NIL
        self.right = NIL

class NodeHeap(Node):
    __slots__ = ["priority"]

    def __init__(self,key=NIL, priority=NIL):
        super().__init__(key)
        self.priority = priority

class BinaryTree():
    def __init__(self):
        self.root = NIL

    def _isnil(self, x):
        if isinstance(x, int):
            return True
        else:
            return False

    def insert(self, key):
        if self.root == NIL:
            self.root = Node(key)
            return

        now = self.root
        while now != NIL:
            parent = now
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                raise

        insert = self.get_newnode(key)
        insert.parent = parent

        if   insert.key < parent.key:
            parent.left = insert
        elif insert.key > parent.key:
            parent.right = insert
        else:
            raise

    def find(self, key):
        now = self.root
        while now != NIL and now.key != key:
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                raise

        return now

    def delete(self, key):
        z = self.find(key)
        if self._isnil(z):
            return

        if z.left == NIL or z.right == NIL:
            y = z
        else:
            y = self.get_successor(z)

        if y.left != NIL:
            x = y.left
        else:
            x = y.right

        if x != NIL:
            x.parent = y.parent

        if y.parent == NIL:
            # delete:root
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        if y != z:
            z.key = y.key

    def get_successor(self, z):
        if z.right != NIL:
            return self.get_minimum(z.right)

        y = z.parent
        while y != NIL and z == y.right:
            z = y
            y = y.parent

        return y

    def get_minimum(self, x):
        while x.left != NIL:
            x = x.left

        return x

    def print_inorder(self):
        self._treewalk_inorder(self.root)
        print()

    def _treewalk_inorder(self, node):
        if self._isnil(node):
            return

        self._treewalk_inorder(node.left)
        print(f" {node.key}", end="")
        self._treewalk_inorder(node.right)

    def print_preorder(self):
        self._treewalk_preorder(self.root)
        print()

    def _treewalk_preorder(self, node):
        if self._isnil(node):
            return

        print(f" {node.key}", end="")
        self._treewalk_preorder(node.left)
        self._treewalk_preorder(node.right)

class Treap(BinaryTree):
    def __init__(self):
        self.root = NIL

    def _right_rotate(self, t):
        s = t.left
        t.left = s.right
        s.right = t
        return s

    def _left_rotate(self, t):
        s = t.right
        t.right = s.left
        s.left = t
        return s

    def insert(self, key, priority):
        self.root = self._insert_main(self.root, key, priority)

    def _insert_main(self, node, key, priority):
        if node == NIL:
            return NodeHeap(key, priority)

        if   key > node.key:
            node.right = self._insert_main(node.right, key, priority)
            if node.priority < node.right.priority:
                node = self._left_rotate(node)
        elif key < node.key:
            node.left = self._insert_main(node.left, key, priority)
            if node.priority < node.left.priority:
                node = self._right_rotate(node)
        else:
            raise

        return node

    def delete(self, key):
        self.root = self._delete_main(self.root, key)

    def _delete_main(self, node, key):
        if node == NIL:
            return node

        if key < node.key:
            node.left = self._delete_main(node.left, key)
        elif key > node.key:
            node.right = self._delete_main(node.right, key)
        else:
            return self._delete_rotate(node, key)

        return node

    def _delete_rotate(self, node, key):
        if node.left == NIL and node.right == NIL:
            return NIL
        elif node.left == NIL:
            node = self._left_rotate(node)
        elif node.right == NIL:
            node = self._right_rotate(node)
        else:
            if node.left.priority > node.right.priority:
                node = self._right_rotate(node)
            else:
                node = self._left_rotate(node)

        return self._delete_main(node, key)


m = int(input())

treap = Treap()

for _ in range(m):

    command, *list_num = input().split()

    if   command == "insert":
        k = int(list_num[0])
        p = int(list_num[1])
        treap.insert(k, p)
    elif command == "find":
        k = int(list_num[0])
        if isinstance(treap.find(k), int):
            print("no")
        else:
            print("yes")
    elif command == "delete":
        k = int(list_num[0])
        treap.delete(k)
    elif command == "print":
        treap.print_inorder()
        treap.print_preorder()
    else:
        raise