human
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...
class
assistant
#Here is the Python code you requested.
 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:
           ...