
from __future__ import annotations

from random import random







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase = None ):
       snake_case_	=				value
       snake_case_	=				random()
       snake_case_	=				None
       snake_case_	=				None



 def __repr__(     self ):
       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 ):
       snake_case_	=				str(self.value ) + ''' '''
       snake_case_	=				str(self.left or '''''' )
       snake_case_	=				str(self.right or '''''' )
       return value + left + right






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  tuple[Node | None, Node | None]:




      """simple docstring"""

      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:
                  snake_case_	,   snake_case_	=				split(root.left , __lowerCamelCase )
                  return left, root
            else:
                  snake_case_	,   snake_case_	=				split(root.right , __lowerCamelCase )
                  return root, right






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Node | None:




      """simple docstring"""

      if (not left) or (not right):  # If one node is None, return the other
            return left or right
      elif left.prior < right.prior:
            snake_case_	=				merge(left.right , __lowerCamelCase )
            return left
      else:
            snake_case_	=				merge(__lowerCamelCase , right.left )
            return right






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Node | None:




      """simple docstring"""

      snake_case_	=				Node(__lowerCamelCase )
      snake_case_	,   snake_case_	=				split(__lowerCamelCase , __lowerCamelCase )
      return merge(merge(__lowerCamelCase , __lowerCamelCase ) , __lowerCamelCase )






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Node | None:




      """simple docstring"""

      snake_case_	,   snake_case_	=				split(__lowerCamelCase , value - 1 )
      snake_case_	,   snake_case_	=				split(__lowerCamelCase , __lowerCamelCase )
      return merge(__lowerCamelCase , __lowerCamelCase )






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE )->  None:




      """simple docstring"""

      if not root:  # None
            return
      else:
            inorder(root.left )
            print(root.value , end=''',''' )
            inorder(root.right )






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Node | None:




      """simple docstring"""

      for arg in args.split():
            if arg[0] == "+":
                  snake_case_	=				insert(__lowerCamelCase , int(arg[1:] ) )

            elif arg[0] == "-":
                  snake_case_	=				erase(__lowerCamelCase , int(arg[1:] ) )

            else:
                  print('''Unknown command''' )

      return root






def 	__lowerCAmelCase   ()->  None:




      """simple docstring"""

      snake_case_	=				None
      print(
          '''enter numbers to create a tree, + value to add value into treap, '''
          '''- value to erase all nodes with value. \'q\' to quit. ''' )

      snake_case_	=				input()
      while args != "q":
            snake_case_	=				interact_treap(__lowerCamelCase , __lowerCamelCase )
            print(__lowerCamelCase )
            snake_case_	=				input()

      print('''good by!''' )


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()



import os






def 	__lowerCAmelCase   ()->  List[Any]:




      """simple docstring"""

      snake_case_	=				os.path.join(os.path.dirname(SCREAMING_SNAKE_CASE ) , '''num.txt''' )
      with open(SCREAMING_SNAKE_CASE ) as file_hand:
            return str(sum(int(SCREAMING_SNAKE_CASE ) for line in file_hand ) )[:10]


if __name__ == "__main__":
   print(solution())