



from __future__ import annotations

from random import random



class 						UpperCAmelCase_					:







							def __init__(     self,    __a = None):

														'''simple docstring'''

														_lowerCAmelCase  :							Tuple				     =					value
														_lowerCAmelCase  :							Dict				     =					random()
														_lowerCAmelCase  :							Node | None				     =					None
														_lowerCAmelCase  :							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'''

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






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''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:
																					_lowerCAmelCase     ,					_lowerCAmelCase  :							Dict				     =					split(root.left       ,				_lowerCamelCase						)
																					return left, root
														else:
																					_lowerCAmelCase     ,					_lowerCAmelCase  :							Union[str, Any]				     =					split(root.right       ,				_lowerCamelCase						)
																					return root, right






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''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:
														_lowerCAmelCase  :							Optional[int]				     =					merge(left.right       ,				_lowerCamelCase						)
														return left
							else:
														_lowerCAmelCase  :							str				     =					merge(_lowerCamelCase       ,				right.left						)
														return right






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							Tuple				     =					Node(_lowerCamelCase						)
							_lowerCAmelCase     ,					_lowerCAmelCase  :							List[Any]				     =					split(_lowerCamelCase       ,				_lowerCamelCase						)
							return merge(merge(_lowerCamelCase       ,				_lowerCamelCase						)       ,				_lowerCamelCase						)






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase     ,					_lowerCAmelCase  :							Optional[Any]				     =					split(_lowerCamelCase       ,				value - 1						)
							_lowerCAmelCase     ,					_lowerCAmelCase  :							List[str]				     =					split(_lowerCamelCase       ,				_lowerCamelCase						)
							return merge(_lowerCamelCase       ,				_lowerCamelCase						)






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




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






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




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

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

														else:
																					print("Unknown command"						)

							return root






def        A       (      ):





							'''simple docstring'''




							_lowerCAmelCase  :							Optional[int]				     =					None
							print(
							    "enter numbers to create a tree, + value to add value into treap, "
							    "- value to erase all nodes with value. 'q' to quit. "						)

							_lowerCAmelCase  :							List[Any]				     =					input()
							while args != "q":
														_lowerCAmelCase  :							Dict				     =					interact_treap(_lowerCamelCase       ,				_lowerCamelCase						)
														print(_lowerCamelCase						)
														_lowerCAmelCase  :							Optional[int]				     =					input()

							print("good by!"						)


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						main()





from __future__ import annotations






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							if not nums:
														raise ValueError("List is empty"						)
							return sum(_lowerCamelCase						) / len(_lowerCamelCase						)


if __name__ == "__main__":
						import doctest

						doctest.testmod()
