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 ... Give me a the Python code you requested?
assistant
#Here is the Python code you requested.
 Node:
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.parent = None
        self.left = self.right = None
    def preorder(self):
        L = [self.key]
        if self.left: L += self.left.preorder()
        if self.right: L += self.right.preorder()
        return L
    def inorder(self):
        L = []
        if self.left: L += self.left.inorder()
        L.append(self.key)
        if self.right: L += self.right.inorder()
        return L

def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s # root of the subtree
def leftRotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s # root of the subtree

def insert(t, key, priority):
    if not t:
        return Node(key, priority) # 葉に到達したら新しい節点を生成して返す
    if key == t.key:
        return t # 重複したkeyは無視
    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 not t:
        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 not t.left and not t.right: # 葉の場合
        return None
    if not t.left: # 右の子のみを持つ場合左回転
        t = leftRotate(t)
    elif not t.right: # 左の子のみを持つ場合右回転
        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, k):
    x = t
    while x:
        if x.key == k:
            return x
        x = x.left if k < x.key else x.right
    return None

t = None
m =...