output_description: 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_.
input_description: 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.
attempt: from random import random
  from collections import deque
  from copy import deepcopy
  import sys
  
  input = sys.stdin.readline
  
  
  class Treap:
      def __init__(self, iterable=None):
          # vertex = [left, right, key, priority, #descendants, sum of descendants]
          self.root = None
          if iterable:
              self._construct(iterable)
  
      def _construct(self, iterable):
          for it in iterable:
              self.insert(it)
  
      def __len__(self):
          return self._count(self.root)
  
      @staticmethod
      def _count(v):
          return v[4] if v is not None else 0
  
      def _rotate(self, v, direction):  # rotate the vertex v to the given direction
          c = v[1 - direction]  # direction == 1: right rotation
          v[1 - direction], t = c[direction], c[1 - direction]
          c[direction] = v
          # update vertex's information
          n_desc, sum_desc = c[4:] = v[4:]
          v[4:] = n_desc - 1 - self._count(t), sum_desc - (c[2] if c[2] else 0) - (
              t[5] if t else 0
          )
          return c  # new parent
  
      def __contains__(self, key):  # check whether the given key is in the treap
          if self.root is None:
              return False
          v = self.root
          while v:
              k = v[2]
              if k == key:
                  return True
              v = v[key > k]  # key > v[2] -> v = v[1] (right child)
          return False
  
      def __getitem__(self, i):  # get the i-th smallest element in the treap
          count = self._count
          if i < 0:
              i = count(self.root) + i
          if i >= count(self.root) or i < 0:
              raise IndexError
          v = self.root
          while True:
              n_left = count(v[0])
              if i == n_left:
                  return v[2]
              elif i > n_left:
                  i -= n_left + 1
                  v = v[1]
              else:
                  v = v[0]
  
      def __repr__(self):  # visualize the treap
          if not self.root:
              return "Treap([])"
          elements = []
          q = deque([self.root])
          while q:
              v = q.popleft()
              if v is None:
                  elements.append(v)
                  continue
              elements.append((v[2], v[3]))
              q.append(v[0])
              q.append(v[1])
          return "Treap({})".format(str(elements))
  
      @classmethod
      def _treap(cls, treapnode):
          tp = cls()
          tp.root = deepcopy(treapnode)
          return tp
  
      def sort(self):
          if not self.root:
              return []
          elements = []
          stack = [(self.root, 0)]
          while stack:
              v, st = stack.pop()
              [left, right, k, _, _, _] = v
              if st == 0:
                  if right:
                      stack.append((right, 0))
                  stack.append((v, 1))
                  if left:
                      stack.append((left, 0))
              if st == 1:
                  elements.append(k)
          return elements
  
      def bisect(self, key):  # bisect_right
          if self.root is None:
              return 0
          v = self.root
          idx = 0
          count = self._count
          while v:
              left, right, k, _, _, _ = v
              if key >= k:
                  idx += count(left) + 1
                  v = right
              else:
                  v = left
          return idx
  
      def insert(self, key, priority=None):
          if priority is None:
              priority = random()
          rotate = self._rotate
          v = self.root
          p = None
          direction = None
          stack = []
          while v:
              direction = key >= v[2]
              stack.append((v, direction))
              v, p = v[direction], v
          v = [None, None, key, priority, 1, key]
          while stack:
              p, direction = stack.pop()
              p[direction] = v
              p[4] += 1
              p[5] += key  # update vertex's information
              if p[3] >= v[3]:
                  break
              v = rotate(p, 1 - direction)
          else:
              self.root = v
          for p, _ in stack:
              p[4] += 1
              p[5] += key  # update vertex's information
          return self.root
  
      def delete(self, key):
          v = self.root
          p = None
          direction = None
          stack = []
          while v:
              if key == v[2]:
                  break  # vertex to be deleted has been found
              direction = key > v[2]
              stack.append((v, direction))
              v, p = v[direction], v
          else:
              return self.root  # the given key is not in the treap
          rotate = self._rotate
          while v[0] or v[1]:  # while v is not a leaf
              left, right, _, _, _, _ = v
              direction = (left[3] > right[3]) if left and right else (right is None)
              p = rotate(v, direction)
              stack.append((p, direction))
              v = p[direction]
          v = None  # delete
          while stack:
              p, direction = stack.pop()
              p[direction] = v
              p[4] -= 1
              p[5] -= key if key else 0  # update vertex's information
              v = p
          self.root = v
          return self.root
  
      def merge(self, other):
          r, o = self.root, other.root
          temp_v = [r, o, None, float("inf"), 1 + r[4] + o[4], r[5] + o[5]]
          virtual = self._treap(temp_v)
          self.root = virtual.delete(None)
          return self.root
  
      def split(self, i):
          count = self._count
          if i < 0:
              i = count(self.root) + i
          if i >= count(self.root) or i < 0:
              raise IndexError
          rotate = self._rotate
          v = self.root
          p = None
          direction = None
          stack = []
          while v:
              n_left = count(v[0])
              direction = i > n_left
              stack.append((v, direction))
              if direction:
                  i -= n_left + 1
              v, p = v[direction], v
          v = [None, None, None, float("inf"), 1, 0]
          while stack:
              p, direction = stack.pop()
              p[direction] = v
              p[4] += 1
              p[5] += 0  # update vertex's information
              v = rotate(p, 1 - direction)
          l, r = v[:2]
          self.root = l
          return self._treap(r)
  
  
  def print_treap(tr):
      preorder = [""]
      inorder = [""]
  
      def dfs(vtx):
          v = str(vtx[2])
          preorder.append(v)
          if vtx[0]:
              dfs(vtx[0])
          inorder.append(v)
          if vtx[1]:
              dfs(vtx[1])
  
      dfs(tr.root)
      print(" ".join(inorder))
      print(" ".join(preorder))
      return
  
  
  m = int(input())
  tr = Treap()
  for _ in range(m):
      (
          query,
          *args,
      ) = input().split()
      if query == "insert":
          k, p = map(int, args)
          tr.insert(k, p)
      elif query == "find":
          k = int(args[0])
          print("yes" if k in tr else "no")
      elif query == "delete":
          k = int(args[0])
          tr.delete(k)
      else:
          print_treap(tr)
  
problem_description: 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 < 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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/ALDS1_8_D_treap)
  
  **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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/ALDS1_8_D_treap_insert)
  
  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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/ALDS1_8_D_rotate)
  
  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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/ALDS1_8_D_insert_rotate)
  
  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 < t.key                               // move to the left child
              t.left = insert(t.left, key, priority)   // update the pointer to the left child
              if t.priority < t.left.priority          // rotate right if the left child has higher priority
                  t = rightRotate(t)
          else                                         // move to the right child
              t.right = insert(t.right, key, priority) // update the pointer to the right child
              if t.priority < t.right.priority         // rotate left if the right child has higher priority
                  t = leftRotate(t)
      
        return t
      
  
  **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                             // search the target recursively
              t.left = delete(t.left, key)
          else 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.
samples: [{"input": "16\n    insert 35 99\n    insert 3 80\n    insert 1 53\n    insert 14 25\n    insert 80 76\n    insert 42 3\n    insert 86 47\n    insert 21 12\n    insert 7 10\n    insert 6 90\n    print\n    find 21\n    find 22\n    delete 35\n    delete 99\n    print", "output": "1 3 6 7 14 21 35 42 80 86\n     35 6 3 1 14 7 21 80 42 86\n    yes\n    no\n     1 3 6 7 14 21 42 80 86\n     6 3 1 80 14 7 21 42 86"}]