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 Node():
    def __init__(self, key, pri):
        self.key = key
        self.pri = pri
        self.left = self.right = None
         
 
def insert(t, key, pri):
    if t == None:
        return Node(key, pri) 
    if key == t.key:
        return t                             
 
    if key < t.key:
        t.left = insert(t.left, key, pri)
        if t.pri < t.left.pri:
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.pri < t.right.pri:
            t = leftRotate(t)
 
    return t
         
def rightRotate(node):
    global root
    a = node.left
    node.left = a.right
    a.right = node
    if node == root:
        root = a
    return a
 
def leftRotate(node):
    global root
    a = node.right
    node.right = a.left
    a.left = node
    if node == root:
        root = a
    return a
     
         
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
     
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)
 
def find(node, key):
    if node == None:
        print('no');return
    if node.key == key:
        print('yes');return
    elif node.key > key:
        find(node.left, key)
    else:
        find(node.right, key)
 
def delete(t, key):
    global root
    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)
    elif key == 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.pri > t.right.pri:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return delete(t, key)
    return t
 
     
 
n = int(input())


root = None


for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':root = insert(root,int(i[0]), int(i[1]))
    elif s[0] == 'f':
        find(root, int(i[0]))
    elif s[0] == 'd':
        delete(root, int(i[0]))
    else:
        ino(root);print();pre(root);print()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,key,pri,left=None,right=None):
        self.left = left
        self.right = right
        self.key = key
        self.pri = pri
 
def insert(t,key,pri):
    if t == None :
        return Node(key,pri)
    if key == t.key :
        return t
    if key < t.key :
        t.left = insert(t.left, key, pri)
        if t.pri < t.left.pri :
            t = rrotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.pri < t.right.pri :
            t = lrotate(t)
    return t
 
 
def rrotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s

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

 
def find(t,key):
    if t == None: return None
    elif t.key == key:return t
    elif t.key > key :return find(t.left,key)
    else: return find(t.right,key)
 
def erase(t, key):
    if t == None : return None
    if key == t.key: 
        if t.left == None and t.right == None:return None
        elif t.left == None : t = lrotate(t)
        elif t.right == None : t = rrotate(t)
        else:
            if t.left.pri > t.right.pri:t = rrotate(t)
            else: t = lrotate(t)
        return erase(t, key)
    elif key < t.key : t.left = erase(t.left, key)
    else : t.right = erase(t.right, key)
    return t
 
def inorder(t):
    if t.left != None:inorder(t.left)
    print(" "+str(t.key), end='')
    if t.right != None: inorder(t.right)
 
def preorder(t):
    print(" "+str(t.key), end='')
    if t.left != None :preorder(t.left)
    if t.right != None : preorder(t.right)

if __name__=="__main__": 
        m=(int)(input())
        root = None
        for i in range(m):
            order = input().split()
            if order[0] == "insert" :root = insert(root,(int)(order[1]),(int)(order[2]))
            elif order[0] == "delete" :root = erase(root,(int)(order[1]))
            elif order[0] == "find" :
                res = find(root,(int)(order[1]))
                if res == None :print("no")
                else:print("yes")
            else:
                inorder(root)
                print()
                preorder(root)
                print()

Submission status: Accepted

Solution code:
import sys


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


def right_rotate(t: Node):
    s = t.left
    t.left = s.right
    s.right = t
    return s


def left_rotate(t: Node):
    s = t.right
    t.right = s.left
    s.left = t
    return s


def insert(t: Node, key: int, pri: int):
    if t is None:
        return Node(key, pri)
    if key == t.key:
        return t
    if key < t.key:
        t.left = insert(t.left, key, pri)
        if t.pri < t.left.pri:
            t = right_rotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.pri < t.right.pri:
            t = left_rotate(t)
    return t


def erase(t: Node, key: int):
    if t is None:
        return None
    if key == t.key:
        if t.left is None and t.right is None:
            return None
        elif t.left is None:
            t = left_rotate(t)
        elif t.right is None:
            t = right_rotate(t)
        else:
            if t.left.pri > t.right.pri:
                t = right_rotate(t)
            else:
                t = left_rotate(t)
        return erase(t, key)
    if key < t.key:
        t.left = erase(t.left, key)
    else:
        t.right = erase(t.right, key)
    return t


def find(t: Node, x: int):
    while t is not None:
        if t.key == x:
            return 1
        elif t.key > x:
            t = t.left
        else:
            t = t.right
    return 0


def inorder(t: Node):
    if t.left is not None:
        inorder(t.left)
    print(" {}".format(t.key), end='')

    if t.right is not None:
        inorder(t.right)
    return


def preorder(t: Node):
    print(" {}".format(t.key), end='')

    if t.left is not None:
        preorder(t.left)
    if t.right is not None:
        preorder(t.right)
    return


def print_key(t: Node):
    inorder(t)
    print("\n", end='')
    preorder(t)
    print("\n", end='')
    return


line = sys.stdin.readline()
n = int(line)
root = None
for i in range(n):
    line = sys.stdin.readline().split()
    if line[0] == 'insert':
        k, p = int(line[1]), int(line[2])
        root = insert(root, k, p)
    elif line[0] == 'delete':
        k = int(line[1])
        root = erase(root, k)
    elif line[0] == 'find':
        k = int(line[1])
        if find(root, k):
            print("yes")
        else:
            print("no")
    else:
        print_key(root)

Submission status: Accepted

Solution code:
import sys
import time
input = sys.stdin.readline

def left_rot(node):
    s = node['right'].copy()
    node['right'] = s['left']#.copy()
    s['left'] = node
    return s

def right_rot(node):
    s = node['left'].copy()
    node['left'] = s['right']#.copy()
    s['right'] = node
    return s

def insert(node,k,p):
    if(node is None):
        child = {
            'left' : None,
            'right' : None,
            'key' : k,
            'priority' : p}
        return child
    if(k == node['key']):
        return node
    # Left side
    if(k < node['key']):
        node['left'] = insert(node['left'],k,p)
        #追加したらあとは優先度による回転を行う
        if(node['priority'] < node['left']['priority']):
            node = right_rot(node)
    # Right side
    else:
        node['right'] = insert(node['right'],k,p)
        #追加したらあとは以下略
        if(node['priority'] < node['right']['priority']):
            node = left_rot(node)

    return node

def find(node, k):
    if(node is None):
        return 'no'
    if(node['key'] == k):
        return 'yes'
    if(k < node['key']):
        return find(node['left'],k)
    else:
        return find(node['right'],k)

def delete(node, k):
    if(node is None):
        return None

    if(node['key'] == k):
        if(node['left'] is None and node['right'] is None):
            return None
        elif(node['left'] is None):
            node = left_rot(node)
        elif(node['right'] is None):
            node = right_rot(node)
        else:
            if(node['left']['priority'] > node['right']['priority']):
                node = right_rot(node)
            else:
                node = left_rot(node)
        return delete(node, k)
    if(k < node['key']):
        node['left'] = delete(node['left'], k)
    else:
        node['right'] = delete(node['right'], k)

    return node

def print_treap(node,values):
    if(node is None):
        return values
    values.append(node['key'])
    values = print_treap(node['left'],values)
    values = print_treap(node['right'],values)
    return values

num = int(input())
req = [input().split() for _ in range(num)]
node = None
values = []
for q in req:
    if(q[0] == 'insert'):
        node = insert(node, int(q[1]),int(q[2]))
    elif(q[0] == 'find'):
        print(find(node,int(q[1])))
    elif(q[0] == 'delete'):
        node = delete(node, int(q[1]))
    else:
        print_treap(node, values)
        print(" "+" ".join(map(str, sorted(values))))
        print(" "+" ".join(map(str, values)))
        values.clear()

Submission status: Accepted

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

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

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

    return t
        
def rightRotate(node):
    global root
    a = node.left
    node.left = a.right
    a.right = node
    if node == root:
        root = a
    return a

def leftRotate(node):
    global root
    a = node.right
    node.right = a.left
    a.left = node
    if node == root:
        root = a
    return a
    
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)

def find(node, key):
    if node == None:
        print('no');return
    if node.key == key:
        print('yes');return
    elif node.key > key:
        find(node.left, key)
    else:
        find(node.right, key)

def delete(t, key):
    global root
    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)
    elif key == 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.pri > t.right.pri:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return delete(t, key)
    return t

    

n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':root = insert(root,int(i[0]), int(i[1]))
    elif s[0] == 'f':
        find(root, int(i[0]))
    elif s[0] == 'd':
        delete(root, int(i[0]))
    else:
        ino(root);print();pre(root);print()

Submission status: Accepted

Solution code:
# coding: utf-8

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

class Treap:
    def __init__(self, root=None):
        self.root = root
    
    def insert(self, node, key, priority):
        if node == None:
            return Node(key, priority)
        if key == node.key:
            return node
        
        if key < node.key:
            node.left = self.insert(node.left, key, priority)
            if node.priority < node.left.priority:
                node = self.rightRotate(node)
        else:
            node.right = self.insert(node.right, key, priority)
            if node.priority < node.right.priority:
                node = self.leftRotate(node)
        return node
            
        
    def rightRotate(self, node):
        tmp = node.left
        node.left = tmp.right
        tmp.right = node
        return tmp
        
    def leftRotate(self, node):
        tmp = node.right
        node.right = tmp.left
        tmp.left = node
        return tmp
    
    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._delete(node, key)
        return node
    
    def _delete(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.priority > node.right.priority:
                node = self.rightRotate(node)
            else:
                node = self.leftRotate(node)
        return self.delete(node, key)
        
    def find(self, node, key):
        if key == node.key:
            return node
        if key < node.key:
            if node.left != None:
                return self.find(node.left, key)
            else:
                return None
        if key > node.key:
            if node.right != None:
                return self.find(node.right, key)
            else:
                return None
    
    def resetAns(self):
        self.ans = []
    
    def getPreorder(self, node):
        self.ans.append(node)
        if node.left != None:
            self.getPreorder(node.left)
        if node.right != None:
            self.getPreorder(node.right)
    
    def getInorder(self, node):
        if node.left != None:
            self.getInorder(node.left)
        self.ans.append(node)
        if node.right != None:
            self.getInorder(node.right)
            
    def printAns(self):
        for nd in self.ans:
            print(" " + str(nd.key),end="")
        print()

m = int(input().rstrip())
tr = Treap()
for i in range(m):
    line = input().rstrip().split()
    if line[0] == "insert":
        tr.root = tr.insert(tr.root, int(line[1]), int(line[2]))
    elif line[0] == "find":
        if tr.find(tr.root, int(line[1])) != None:
            print("yes")
        else:
            print("no")
    elif line[0] == "delete":
        tr.root = tr.delete(tr.root, int(line[1]))
    else:
        tr.resetAns()
        tr.getInorder(tr.root)
        tr.printAns()
        tr.resetAns()
        tr.getPreorder(tr.root)
        tr.printAns()

Submission status: Accepted

Solution code:
import sys, os
from io import StringIO

class BinaryTree:

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

    def __init__(self):
        self.root = None
        self.output = StringIO()


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

    def _insert_main(self, key, node, priority):
        if node is None:
            return self.Node(key, priority)
        else:
            if key > node.key:
                node.right = self._insert_main(key, node.right, priority)
                if node.priority < node.right.priority:
                    node = self.rotate_left(node)
            else:
                node.left = self._insert_main(key, node.left, priority)
                if node.priority < node.left.priority:
                    node = self.rotate_right(node)
            return node


    def rotate_right(self, base):
        left_node = base.left
        # left.right = base
        # base.left = replace
        base.left = left_node.right
        left_node.right = base
        return left_node

    def rotate_left(self, base):
        right_node = base.right
        # replace = right.left
        # right.left = base
        # base.right = replace
        base.right = right_node.left
        right_node.left = base
        return right_node

    def ini_print_inorder(self):
        self.output = StringIO()
        self._print_inorder(self.root)
        return self.output.getvalue()

    def ini_print_preorder(self):
        self.output = StringIO()
        self._print_preorder(self.root)
        return self.output.getvalue()

    def ini_print_postorder(self):
        self.output = StringIO()
        self._print_postorder(self.root)
        return self.output.getvalue()

    def _print_inorder(self, node):
        if node is not None:
            self._print_inorder(node.left)
            print(node.key, end = " ", file = self.output)
            self._print_inorder(node.right)

    def _print_preorder(self, node):
        if node is not None:
            print(node.key, end = " ", file = self.output)
            self._print_preorder(node.left)
            self._print_preorder(node.right)

    def _print_postorder(self, node):
        if node is not None:
            self._print_preorder(node.left)
            self._print_preorder(node.right)
            print(node.key, end = " ", file = self.output)

    def test_insert(self, keys):
        for k in keys:
            self.insert(k)

    def ini_find(self, key):
        print(self.find(key))

    def find(self, key):
        root = self.root
        while root is not None:
            if key == root.key:
                return "yes"
            elif key < root.key:
                root = root.left
            else:
                root = root.right
        return "no"

    def get_successor(self, node):
        parent = node
        while True:
            node = node.left
            if node is None:
                return parent, parent.parent
            parent = node
        return None

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

    def _delete_main(self, key, node):
        if node:
            if key > node.key:
                node.right = self._delete_main(key, node.right)
            elif key < node.key:
                node.left = self._delete_main(key, node.left)
            else:
                if node.right is None and node.left is None:
                    return None
                elif node.right is None:
                    node = self.rotate_right(node)
                elif node.left is None:
                    node = self.rotate_left(node)
                else:
                    if node.left.priority > node.right.priority:
                        node = self.rotate_right(node)
                    else:
                        node = self.rotate_left(node)
                node = self._delete_main(key, node)
        return node

    def _search_min(self, node):
        if node.left is None:
            return node.key
        return self._search_min(node.left)

    def _delete_min(self, node):
        if node.left is None:
            return node.right
        node.left = self._delete_min(node.left)
        return node



b = BinaryTree()
length = int(input())
for _ in range(length):
    comm = input()
    if comm[0] == "i":
        com, num, pri = comm.split(" ")
        b.insert(int(num), int(pri))
    elif comm[0] == "p":
        print(" ", end = "")
        print(b.ini_print_inorder()[:-1])
        print(" ", end = "")
        print(b.ini_print_preorder()[:-1])

    elif comm[0] == "f":
        com, num = comm.split(" ")
        b.ini_find(int(num))
    else:
        com, num = comm.split(" ")
        b.delete(int(num))

Submission status: Accepted

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


def insert(root,node):#rootを根に持つ２分探索木にnodeを追加する
    if(root.key <= node.key):
        if(root.right is None):
            root.right=node
            node.parent=root
            node.rightflag=1
        else:
            insert(root.right,node)
    
    else:
        if(root.left is None):
            root.left=node
            node.parent=root
            node.rightflag=0
        else:
            insert(root.left,node)


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

    elif(root.key < key):
        if(root.right is not None):
            return find(root.right,key)
        else:
            return None

    else:
        if(root.left is not None):
            return find(root.left,key)
        else:
            return None







                   
            
        



    

def Preorder(root,order):
    order.append(root.key)
    if(root.left is not None):
        Preorder(root.left,order)
    
    if(root.right is not None):
        Preorder(root.right,order)




def Inorder(root,order):
    if(root.left is not None):
        Inorder(root.left,order)
    
    order.append(root.key)


    if(root.right is not None):
        Inorder(root.right,order)



def right_rotate(node,Root):#nodeのparentの場所にnodeを移動させる(二分木の条件を保ちつつ)
    if(node.parent==None):#与えられたnodeがrootだった場合0を返す
        return 0
    
    node.parent.left=node.right#NoneでもこれでOk
    if(node.right is not None):
        node.right.parent=node.parent
        node.right.rightflag=0
    

    if(node.parent.parent is not None):
        tmp_parent=node.parent.parent
        node.parent.parent=node
        node.rightflag=node.parent.rightflag
        node.parent.rightflag=1
        node.right=node.parent
        node.parent=tmp_parent
        if(node.rightflag):
            tmp_parent.right=node
        else:
            tmp_parent.left=node
    else:
        node.parent.parent=node
        node.rightflag=-1
        node.parent.rightflag=1
        node.right=node.parent
        node.parent=None
        Root[0]=node
    
    return 1


def left_rotate(node,Root):#nodeのparentの場所にnodeを移動させる(二分木の条件を保ちつつ)
    if(node.parent==None):#与えられたnodeがrootだった場合0を返す
        return 0
    
    node.parent.right=node.left#NoneでもこれでOk
    if(node.left is not None):
        node.left.parent=node.parent
        node.left.rightflag=1
    

    if(node.parent.parent is not None):
        tmp_parent=node.parent.parent
        node.parent.parent=node
        node.rightflag=node.parent.rightflag
        node.parent.rightflag=0
        node.left=node.parent
        node.parent=tmp_parent
        if(node.rightflag):
            tmp_parent.right=node
        else:
            tmp_parent.left=node
    else:
        node.parent.parent=node
        node.rightflag=-1
        node.parent.rightflag=0
        node.left=node.parent
        node.parent=None
        Root[0]=node
    
    return 1


def delete(Root,key):
    if(Root[0] is None):
        pass
    else:
        target=find(Root[0],key)
        if(target is None):
            pass
        else:
            while( target.left is not None or target.right is not None):
                if(target.left is not None and target.right is not None):
                    if(target.left.priority <= target.right.priority):
                        left_rotate(target.right,Root)
                    else:
                        right_rotate(target.left,Root)
                
                
                elif(target.left is not None):
                    right_rotate(target.left,Root)
                elif(target.right is not None):
                    left_rotate(target.right,Root)        
            
            if(target.rightflag==1):
                target.parent.right=None
            elif(target.rightflag==0):
                target.parent.left=None
            else:
                Root[0]=None


n=int(input())
root=None

for loop in range(n):
    ope=input().split()

    if(ope[0]=="insert"):
        tmp_node=Node(int(ope[1]),int(ope[2]))
        try:
            insert(root,tmp_node)
            Root=[root]
            while(tmp_node.parent.priority <tmp_node.priority):
                if(tmp_node.rightflag):
                    left_rotate(tmp_node,Root)
                else:
                    right_rotate(tmp_node,Root)
            root=Root[0]
        except:
            root=tmp_node

    elif(ope[0]=="rotate"):
        if(root is not None):
            target=find(root,int(ope[1]))
            if(target is not None):
                Root=[root]
                left_rotate(target,Root)
                root=Root[0]
    
    elif(ope[0]=="find"):
        try:
            if(find(root,int(ope[1])) is not None):
                print("yes")

            else:
                print("no")
        except:
            print("no")
    
    elif(ope[0]=="delete"):
        Root=[root]
        delete(Root,int(ope[1]))
        root=Root[0]

    else:
        in_order=[]
        p_order=[]

        
        Inorder(root,in_order)
        Preorder(root,p_order)

        for x in in_order:
            print(f" {x}",end="")
            
        print()
        for x in p_order:
            print(f" {x}",end="")
        print()