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 < u.key$ and if $v$ is a right child of $u$, then $u.key < v.key$  heap property. If $v$ is a child of $u$, then $v.priority < u.priority$  This combination of properties is why the tree is called Treap (tree + heap). An example of Treap is shown in the following figure.  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 < t.key                               // move to the left child
        t.left = insert(t.left, key, priority)   // update the pointer to the left child
        if t.priority < t.left.priority          // rotate right if the left child has higher priority
            t = rightRotate(t)
    else                                         // move to the right child
        t.right = insert(t.right, key, priority) // update the pointer to the right child
        if t.priority < t.right.priority         // rotate left if the right child has higher priority
            t = leftRotate(t)

  return t  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                             // search the target recursively
        t.left = delete(t.left, key)
    else 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.

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

class Tree:
    def __init__(self):
        self.root = None

    def leftRotate(self, t:Node):
        s:Node = t.right
        t.right = s.left
        s.left = t
        if t.key == self.root.key:
            self.root = s
        return s

    def rightRotate(self, t:Node):
        s:Node = t.left
        t.left = s.right
        s.right = t
        if t.key == self.root.key:
            self.root = s        
        return s

    def insert(self, t:Node, key:int, priority:int):
        if not self.root:
            self.root = Node(key, priority)
            return self.root
        if not t:
            return Node(key, priority)
        if key == t.key:
            return t
        if key < t.key:
            t.left = self.insert(t.left, key, priority)
            if t.priority < t.left.priority:
                t = self.rightRotate(t)
        else:
            t.right = self.insert(t.right, key, priority)
            if t.priority < t.right.priority:
                t = self.leftRotate(t)
        return t

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

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


def Preorder(target:Node):
    yield target.key
    if target.left != None:
        yield from Preorder(target.left)
    if target.right != None:
        yield from Preorder(target.right)

def Inorder(target:Node):
    if target.left != None:
        yield from Inorder(target.left)
    yield target.key
    if target.right != None:
        yield from Inorder(target.right)

def find(target:Node,findkey:int):
    return node_of_key(target, findkey) != None

def node_of_key(target:Node,findkey:int):
    if target.key == findkey:
        return target
    elif target.key > findkey:
        if target.left:
            return node_of_key(target.left, findkey)
    else:
        if target.right:
            return node_of_key(target.right, findkey)
    return None

def min_value_node_of_tree(root:Node):
    if root.left == None:
        return root
    else:
        return min_value_node_of_tree(root.left)


from sys import stdin
tree = Tree()
n = int(input())
lines = stdin.readlines()
for line in lines:
    proc,*param = line.split()
    if proc == "insert":
        if not tree.root:
            tree.root = Node(int(param[0]), int(param[1]))
        else:
            tree.insert(tree.root, int(param[0]), int(param[1]))
    elif proc == "find":
        print("yes" if find(tree.root, int(param[0])) else "no")
    elif proc == "delete":
        tree.delete(tree.root, int(param[0]))
    else:
        print(" ",end="")
        print(*Inorder(tree.root))
        print(" ",end="")
        print(*Preorder(tree.root))

Solution (Python):
class Node:
    def __init__(self, k, p):
        self.k, self.p = k, p
        self.left, self.right = None, None

class Treap:
    def __init__(self):
        self.root = None
    
    def insert(self, k, p):
        self.root = self.__insert(self.root, k, p)

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

    def __insert(self, t, k , p):
        if t == None:
            return Node(k, p)
        if k == t.k:
            return t
        
        if k < t.k:
            t.left = self.__insert(t.left, k, p)
            if t.p < t.left.p:
                t = self.rightRotate(t)
        else:
            t.right = self.__insert(t.right, k, p)
            if t.p < t.right.p:
                t = self.leftRotate(t)
        return t
    
    def delete(self, k):
        self.root = self._delete(k)
        
    def _delete(self, k, t = -1):
        if t == -1:
            t = self.root
        
        if t == None:
            return None
        if k < t.k:
            t.left = self._delete(k, t.left)
        elif k > t.k:
            t.right = self._delete(k, t.right)
        else:
            return self.__delete(t, k)
        return t
    
    def __delete(self, t, k):
        if t.left == None and t.right == None:
            return None
        elif t.left == None:
            t = self.leftRotate(t)
        elif t.right == None:
            t = self.rightRotate(t)
        else:
            if t.left.p > t.right.p:
                t = self.rightRotate(t)
            else:
                t = self.leftRotate(t)
        return self._delete(k, t)

    def find(self, k, t = -1):
        if t == -1:
            t = self.root
        if t == None:
            return None
        if k < t.k:
            return self.find(k, t.left)
        elif k > t.k:
            return self.find(k, t.right)
        else:
            return t
    
    def preOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        print("", r.k, end = '')
        self.preOrder(r.left)
        self.preOrder(r.right)
    
    def inOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        self.inOrder(r.left)
        print("", r.k, end = '')
        self.inOrder(r.right)
    
    def print(self):
        self.inOrder()
        print()
        self.preOrder()
        print()

tree = Treap()
for _ in range(int(input())):
    In = input().split()
    if In[0][0] == 'i':
        tree.insert(int(In[1]), int(In[2]))
    elif In[0][0] == 'p':
        tree.print()
    elif In[0][0] == 'f':
        print(['no', 'yes'][tree.find(int(In[1])) != None])
    elif In[0][0] == 'd':
        tree.delete(int(In[1]))

Solution (Python):
class Node():
    def __init__(self, key, priority, parent, left, right):
        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 == None:
        return Node(key, priority, None, None, None)
    
    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)
    
    if key > t.key:
        t.right = insert(t.right, key, priority)
        if t.priority < t.right.priority:
            t = LeftRotate(t)

    return t

def delete(t, key):
    if t == 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 == None and t.right == None:
        return None
    elif t.left == None:
        t = LeftRotate(t)
    elif t.right == 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 t == None:
        print("no")
        return 

    if key == t.key:
        print("yes")
    elif key < t.key:
        find(t.left, key)
    elif key > t.key:
        find(t.right, key)

def print_inorder(t):
    if t == None:
        return
    
    print_inorder(t.left)
    print(" "+str(t.key), end = "")
    print_inorder(t.right)

def print_preorder(t):
    if t == None:
        return 
    print(" "+str(t.key), end = "")
    print_preorder(t.left)
    print_preorder(t.right)

def Main():
    N = int(input())
    t = None

    for i in range(N):
        ope, *arg = input().split()

        if ope == "insert":
            key, priority = map(int, arg)
            t = insert(t, key, priority)

        elif ope == "delete":
            key = int(arg[0])
            t = delete(t, key)

        elif ope == "find":
            key = int(arg[0])
            find(t, key)

        elif ope == "print":
            print_inorder(t)
            print()
            print_preorder(t)
            print()

Main()

Solution (Python):
from random import random
from collections import deque
from copy import deepcopy
import sys
input = sys.stdin.readline

class Treap:
    def __init__(self, iterable=None):
        
        self.root = None
        if iterable: self._construct(iterable)
    
    def _construct(self, iterable):
        for it in iterable: self.insert(it)
    
    def __len__(self): return self._count(self.root)
    
    @staticmethod
    def _count(v): return v[4] if v is not None else 0

    def _rotate(self, v, direction): 
        c = v[1 - direction] 
        v[1 - direction], t = c[direction], c[1 - direction]
        c[direction] = v
        
        n_desc, sum_desc = c[4:] = v[4:]
        v[4:] = n_desc - 1 - self._count(t), sum_desc - (c[2] if c[2] else 0) - (t[5] if t else 0)
        return c 
    
    def __contains__(self, key): 
        if self.root is None: return False
        v = self.root
        while v:
            k = v[2]
            if k == key: return True
            v = v[key > k] 
        return False
    
    def __getitem__(self, i): 
        count = self._count
        if i < 0: i = count(self.root) + i
        if i >= count(self.root) or i < 0: raise IndexError
        v = self.root
        while True:
            n_left = count(v[0])
            if i == n_left: return v[2]
            elif i > n_left: i -= n_left + 1; v = v[1]
            else: v = v[0]
    
    def __repr__(self): 
        if not self.root: return 'Treap([])'
        elements = []
        q = deque([self.root])
        while q:
            v = q.popleft()
            if v is None: elements.append(v); continue
            elements.append((v[2], v[3]))
            q.append(v[0]); q.append(v[1])
        return 'Treap({})'.format(str(elements))
    
    @classmethod
    def _treap(cls, treapnode):
        tp = cls(); tp.root = deepcopy(treapnode)
        return tp
            
    def sort(self):
        if not self.root: return []
        elements = []
        stack = [(self.root, 0)]
        while stack:
            v, st = stack.pop()
            [left, right, k, _, _, _] = v
            if st == 0:
                if right: stack.append((right, 0))
                stack.append((v, 1))
                if left: stack.append((left, 0))
            if st == 1: elements.append(k)
        return elements
    
    def bisect(self, key): 
        if self.root is None: return 0
        v = self.root; idx = 0
        count = self._count
        while v:
            left, right, k, _, _, _ = v
            if key >= k: idx += count(left) + 1; v = right
            else: v = left
        return idx
    
    def insert(self, key, priority=None):
        if priority is None: priority = random()
        rotate = self._rotate
        v = self.root; p = None; direction = None
        stack = []
        while v:
            direction = (key >= v[2])
            stack.append((v, direction))
            v, p = v[direction], v
        v = [None, None, key, priority, 1, key]
        while stack:
            p, direction = stack.pop()
            p[direction] = v
            p[4] += 1; p[5] += key 
            if p[3] >= v[3]: break
            v = rotate(p, 1 - direction)
        else: self.root = v
        for p, _ in stack: p[4] += 1; p[5] += key 
        return self.root
    
    def delete(self, key):
        v = self.root; p = None; direction = None
        stack = []
        while v:
            if key == v[2]: break 
            direction = (key > v[2])
            stack.append((v, direction))
            v, p = v[direction], v
        else: return self.root 
        rotate = self._rotate
        while v[0] or v[1]: 
            left, right, _, _, _, _ = v
            direction = (left[3] > right[3]) if left and right else (right is None)
            p = rotate(v, direction)
            stack.append((p, direction)); v = p[direction]
        v = None 
        while stack:
            p, direction = stack.pop()
            p[direction] = v
            p[4] -= 1; p[5] -= (key if key else 0) 
            v = p
        self.root = v
        return self.root
    
    def merge(self, other):
        r, o = self.root, other.root
        temp_v = [r, o, None, float('inf'), 1 + r[4] + o[4], r[5] + o[5]]
        virtual = self._treap(temp_v)
        self.root = virtual.delete(None)
        return self.root
    
    def split(self, i):
        count = self._count
        if i < 0: i = count(self.root) + i
        if i >= count(self.root) or i < 0: raise IndexError
        rotate = self._rotate
        v = self.root; p = None; direction = None
        stack = []
        while v:
            n_left = count(v[0])
            direction = (i > n_left)
            stack.append((v, direction))
            if direction: i -= n_left + 1
            v, p = v[direction], v
        v = [None, None, None, float('inf'), 1, 0]
        while stack:
            p, direction = stack.pop()
            p[direction] = v
            p[4] += 1; p[5] += 0 
            v = rotate(p, 1 - direction)
        l, r = v[:2]
        self.root = l
        return self._treap(r)

def print_treap(tr):
    preorder = ['']
    inorder = ['']
    def dfs(vtx):
        v = str(vtx[2])
        preorder.append(v)
        if vtx[0]: dfs(vtx[0])
        inorder.append(v)
        if vtx[1]: dfs(vtx[1])
    dfs(tr.root)
    print(' '.join(inorder))
    print(' '.join(preorder))
    return
    
m = int(input())
tr = Treap()
for _ in range(m):
    query, *args, = input().split()
    if query == 'insert':
        k, p = map(int, args)
        tr.insert(k, p)
    elif query == 'find':
        k = int(args[0])
        print('yes' if k in tr else 'no')
    elif query == 'delete':
        k = int(args[0])
        tr.delete(k)
    else:
        print_treap(tr)

Solution (Python):


class TreapNode:
    def __init__(self, id, priority):
        self.id = id
        self.priority = priority
        self.left = None
        self.right = None
    
    def __str__(self):
        return 'id={}, priority={}'.format(self.id, self.priority)


    def _rotate_left(self):
        r = self.right
        self.right = r.left
        r.left = self
        return r
    
    def _rotate_right(self):
        l = self.left
        self.left = l.right
        l.right = self
        return l
    
    
    def _delete_node(self):
        if self.left is None and self.right is None:
            return None
        elif self.left is None:
            node = self._rotate_left()
        elif self.right is None:
            node = self._rotate_right()
        else:
            if self.left.priority < self.right.priority:
                node = self._rotate_left()
            else:
                node = self._rotate_right()
                
        return node.delete(self.id)

        
    def insert(self, id, priority):
        if self.id == id:
            return self
            
        if id < self.id:
            if self.left:
                self.left = self.left.insert(id, priority)
            else:
                self.left = TreapNode(id, priority)
            
            if self.priority < self.left.priority:
                return self._rotate_right()
        else:
            if self.right:
                self.right = self.right.insert(id, priority)
            else:
                self.right = TreapNode(id, priority)
                
            if self.priority < self.right.priority:
                return self._rotate_left()
                
        return self

    def delete(self, id):
        if id < self.id:
            if self.left:
                self.left = self.left.delete(id)
        elif id > self.id:
            if self.right:
                self.right = self.right.delete(id)
        else:
            return self._delete_node()
            
        return self
    
                
    def inorder(self, result):
        if self.left:
            self.left.inorder(result)
            
        result.append(self.id)
        
        if self.right:
            self.right.inorder(result)
    
    
    def preorder(self, result):
        result.append(self.id)
        
        if self.left:
            self.left.preorder(result)
            
        if self.right:
            self.right.preorder(result)

    def find(self, id):
        if self.id == id:
            return True
        if id < self.id:
            if self.left and self.left.find(id):
                return True
        else:
            if self.right and self.right.find(id):
                return True
        return False

class Treap:
    def __init__(self):
        self.root = None
    
    def insert_node(self, id, priority):
        if self.root:
            self.root = self.root.insert(id, priority)
        else:
            self.root = TreapNode(id, priority)
    
    def delete_node(self, id):
        if self.root:
            self.root = self.root.delete(id)
    
    def find_node(self, id):
        if self.root:
            return self.root.find(id)
        else:
            return False
            
    def walk_inorder(self):
        result = []
        if self.root:
            self.root.inorder(result)
        return result
    
    def walk_preorder(self):
        result = []
        if self.root:
            self.root.preorder(result)
        return result
    

def main():
    n = int(input())
    treap = Treap()
    
    for _ in range(n):
        cmd = input()
        if cmd[0] == 'p':
            result = treap.walk_inorder()
            print('', *result)
            
            result = treap.walk_preorder()
            print('', *result)

        elif cmd[0] == 'i':
            id, priority = [int(i) for i in cmd.split()[1:3]]
            treap.insert_node(id, priority)
            
        elif cmd[0] == 'd':
            id = int(cmd.split()[1])
            treap.delete_node(id)
            
        elif cmd[0] == 'f':
            id = int(cmd.split()[1])
            if treap.find_node(id):
                print('yes')
            else:
                print('no')

if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def rotate(nd, d):
    c = nd[d]
    if d:
        nd[1] = c[0]
        c[0] = nd
    else:
        nd[0] = c[1]
        c[1] = nd
    return c


root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]
    nd = [None, None, val, pri]
    while st:
        x = st.pop(); d = dr.pop()
        c = x[d] = nd
        if x[3] >= c[3]:
            break
        rotate(x, d)
    else:
        root = nd

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
    return x

def delete(val):
    global root
    x = root

    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
    else:
        root = __delete(x)

def find(val):
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0]:
            dfs(nd[0])
        s1.append(v)
        if nd[1]:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    elif cmd == "find":
        ans.append("yes" if find(int(V[0])) else "no")
    elif cmd == "delete":
        delete(int(V[0]))
    else:
        val, pri = map(int, V)
        insert(val, pri)
write("\n".join(ans))
write("\n")

Solution (Python):
class Node:
    def __init__(self, key, pri):
        self.left = None
        self.right = None
        self.key = key
        self.pri = pri

    def print_pre(self):
        yield self.key
        if self.left:
            for k in self.left.print_pre(): yield k
        if self.right:
            for k in self.right.print_pre(): yield k

    def print_in(self):
        if self.left:
            for k in self.left.print_in(): yield k
        yield self.key
        if self.right:
            for k in self.right.print_in(): yield k

class Tree:
  root = None

  def rightRotate(self, node):
    s = node.left
    node.left = s.right
    s.right = node
    if self.root == node:
      self.root = s
    return s

  def leftRotate(self, node):
    s = node.right
    node.right = s.left
    s.left = node
    if self.root == node:
      self.root = s
    return s

  def insert1(self, node, key, pri):
    if node == None:
      return Node(key, pri)
    elif key == node.key:
      return node

    elif key < node.key:
      node.left = self.insert1(node.left, key, pri)
      if node.pri < node.left.pri:
        node = self.rightRotate(node)
    else:
      node.right = self.insert1(node.right, key, pri)
      if node.pri < node.right.pri:
        node = self.leftRotate(node)
    return node

  def insert(self, key, pri):
    self.insert1(self.root, key, pri)
    if self.root == None:
      self.root = Node(key, pri)

  def delete(self, node, key):
    if node == None:
      return None
    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.delete1(node, key)
    return node

  def delete1(self, node, key):
    if node.left == None and node.right == None:
      return None
    elif node.left == None:
      node = self.leftRotate(node)
    elif node.right == None:
      node = self.rightRotate(node)
    else:
      if node.left.pri > node.right.pri:
        node = self.rightRotate(node)
      else:
        node = self.leftRotate(node)
    return self.delete(node, key)

  def find(self, key):
        y = None
        x = self.root
        while x:
            y = x
            if key == x.key:
              break
            elif key < x.key:
              x = x.left
            else:
              x = x.right
            
        if key == y.key:
            return y

  def print(self):
        print(' ', end='')
        print(*self.root.print_in())
        print(' ', end='')
        print(*self.root.print_pre())

tree = Tree()
m = int(input())

while m:
  l = input().split()
  if len(l) == 3:
    tree.insert(int(l[1]), int(l[2]))
  elif len(l) == 2 and l[0] == "find":
    y = tree.find(int(l[1]))
    if y:
      print("yes")
    else:
      print("no")
  elif len(l) == 2 and l[0] == "delete":
    tree.delete(tree.root, int(l[1]))
  else:
    tree.print()
  m -= 1