from __future__ import annotations
from typing import TypeVar, Optional, Generic, TYPE_CHECKING

if TYPE_CHECKING:
    S = TypeVar( 'S' )
    class Tree:
        def rotate_left( self: S ) -> S: return self
        def rotate_right( self: S ) -> S: return self

else:
    Tree = __import__( 'sol_import' ).do( 'r2_rotate' ).Tree
    T = TypeVar( 'T' )

class Treap( Tree, Generic[ T ] ):
    def __init__( self, key: T, priority: int ):
        self.left  : Optional[ Treap[ T ] ] = None
        self.right : Optional[ Treap[ T ] ] = None
        self.priority = priority
        self.key = key

    def _insert( node: Optional[ Treap[ T ] ], key: T, prio: int ) -> Treap[ T ]:
        if node is None:
            return Treap( key, prio )
        else:
            return node.insert( key, prio )

    def _fix_right( self ) -> Treap[ T ]:
        assert self.right is not None

        if self.priority > self.right.priority:
            return self
        else:
            return self.rotate_right()

    def _fix_left( self ) -> Treap[ T ]:
        assert self.left is not None

        if self.priority > self.left.priority:
            return self
        else:
            return self.rotate_left()

    def insert( self, key: T, prio: int ) -> Treap[ T ]:
        if key > self.key:
            self.right = Treap._insert( self.right, key, prio )
            return self._fix_right()
        else:
            self.left = Treap._insert( self.left, key, prio )
            return self._fix_left()