class Node:
    Node *left
    Node *right
    key
    pri

class Treap:
    Node *root

    # 再帰的に挿入位置を探索
    insert(Node *t, key, pri):
        # 葉に達したらノードを生成して返す
        if t = NULL: 
            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

    # 対象を再帰的に探索
    erase(Node *t, key):
        if t = NULL:
            return NULL

        if key = t.key # t が削除対象
            if t.left = NULL and t.right = NULL: # tが葉:
                return NULL
            else if t.left = NULL:               # tがただ１つの右の子を持つ
                t ← leftRotate(t)
            else if t.right = NULL:              # tがただ１つの左の子を持つ
                t ← rightRotate(t)
            else:                                # tが２つの子をもつ
                # 優先度が高い子を持ち上げる
                if t.left.pri > t.right.pri
                    t ← rightRotate(t)
                else:
                    t ← leftRotate(t)
            return erase(t, key)

         # 対象を再帰的に探索
         if key < t.key:
             t.left ← erase(t.left, key)
         else:
             t.right ← erase(t.right, key)

         return t