





from __future__ import annotations

from random import random



class    A__  :





      def __init__(					self			,				A_ = None  ):
       '''simple docstring'''




       UpperCamelCase      :   Any			      =  value
       UpperCamelCase      :   List[Any]			      =  random()
       UpperCamelCase      :   Node | None			      =  None
       UpperCamelCase      :   Node | None			      =  None





      def __repr__(					self  ):
       '''simple docstring'''




       from pprint import pformat

       if self.left is None and self.right is None:
        return F"""'{self.value}: {self.prior:.5}'"""
       else:
        return pformat(
            {F"""{self.value}: {self.prior:.5}""": (self.left, self.right)}			,				indent=1  )





      def __str__(					self  ):
       '''simple docstring'''




       UpperCamelCase      :   str			      =  str(self.value  ) + " "
       UpperCamelCase      :   int			      =  str(self.left or ""  )
       UpperCamelCase      :   Optional[Any]			      =  str(self.right or ""  )
       return value + left + right



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase	)		->					tuple[Node | None, Node | None]:
 if root is None:  # None tree is split into 2 Nones
  return None, None
 elif root.value is None:
  return None, None
 else:
  if value < root.value:
   UpperCamelCase      ,       UpperCamelCase      :   List[str]			      =  split(root.left				,  _lowerCAmelCase	)
   return left, root
  else:
   UpperCamelCase      ,       UpperCamelCase      :   str			      =  split(root.right				,  _lowerCAmelCase	)
   return root, right



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase	)		->					Node | None:
 if (not left) or (not right):  # If one node is None, return the other
  return left or right
 elif left.prior < right.prior:
  UpperCamelCase      :   List[str]			      =  merge(left.right				,  _lowerCAmelCase	)
  return left
 else:
  UpperCamelCase      :   Tuple			      =  merge(_lowerCAmelCase				,  right.left	)
  return right



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase	)		->					Node | None:
 UpperCamelCase      :   Any			      =  Node(_lowerCAmelCase	)
 UpperCamelCase      ,       UpperCamelCase      :   Union[str, Any]			      =  split(_lowerCAmelCase				,  _lowerCAmelCase	)
 return merge(merge(_lowerCAmelCase				,  _lowerCAmelCase	)				,  _lowerCAmelCase	)



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase	)		->					Node | None:
 UpperCamelCase      ,       UpperCamelCase      :   Any			      =  split(_lowerCAmelCase				,  value - 1	)
 UpperCamelCase      ,       UpperCamelCase      :   Any			      =  split(_lowerCAmelCase				,  _lowerCAmelCase	)
 return merge(_lowerCAmelCase				,  _lowerCAmelCase	)



def 						A_							(	_lowerCAmelCase	)		->					None:
 if not root:  # None
  return
 else:
  inorder(root.left	)
  print(root.value				,  end=","	)
  inorder(root.right	)



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase	)		->					Node | None:
 for arg in args.split():
  if arg[0] == "+":
   UpperCamelCase      :   str			      =  insert(_lowerCAmelCase				,  int(arg[1:]	)	)

  elif arg[0] == "-":
   UpperCamelCase      :   Optional[int]			      =  erase(_lowerCAmelCase				,  int(arg[1:]	)	)

  else:
   print("Unknown command"	)

 return root



def 						A_							(	)		->					None:
 UpperCamelCase      :   Tuple			      =  None
 print(
     "enter numbers to create a tree, + value to add value into treap, "
     "- value to erase all nodes with value. 'q' to quit. "	)

 UpperCamelCase      :   Dict			      =  input()
 while args != "q":
  UpperCamelCase      :   Any			      =  interact_treap(_lowerCAmelCase				,  _lowerCAmelCase	)
  print(_lowerCAmelCase	)
  UpperCamelCase      :   str			      =  input()

 print("good by!"	)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()







def 						A_							(	_lowerCAmelCase	)		->					bool:
 UpperCamelCase      :   List[Any]			      =  0
 for ch in input_str:
  UpperCamelCase      :   Optional[Any]			      =  ord(_lowerCAmelCase	)
  UpperCamelCase      :   Optional[Any]			      =  pow(2				,  _lowerCAmelCase	)

  # If we already turned on bit for current character's unicode
  if bitmap >> ch_unicode & 1 == 1:
   return False
  bitmap |= ch_bit_index_on
 return True


if __name__ == "__main__":
    import doctest

    doctest.testmod()
