






from __future__ import annotations

from random import random


class 					_snake_case						:






	def __init__(		self					,UpperCamelCase = None       )						->    Union[str, Any]:
					snake_case__      :Optional[Any]         =   value
					snake_case__      :Optional[int]         =   random()
					snake_case__      :Node | None         =   None
					snake_case__      :Node | None         =   None






	def __repr__(		self       )						->    str:
					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       )						->    str:
					snake_case__      :List[Any]         =   str(self.value       ) + " "
					snake_case__      :List[Any]         =   str(self.left or ""       )
					snake_case__      :Dict         =   str(self.right or ""       )
					return value + left + right





def 					lowercase_ (    __snake_case     :							Node | None	,	__snake_case     :							int      )     -> 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__      :Union[str, Any]         =   split(root.left	,	__snake_case      )
												return left, root
								else:
												snake_case__      :int         =   split(root.right	,	__snake_case      )
												return root, right





def 					lowercase_ (    __snake_case     :							Node | None	,	__snake_case     :							Node | None      )     -> 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__      :List[str]         =   merge(left.right	,	__snake_case      )
								return left
				else:
								snake_case__      :Dict         =   merge(__snake_case	,	right.left      )
								return right





def 					lowercase_ (    __snake_case     :							Node | None	,	__snake_case     :							int      )     -> Node | None:





				'''simple docstring'''


				snake_case__      :Optional[int]         =   Node(__snake_case      )
				snake_case__      :Dict         =   split(__snake_case	,	__snake_case      )
				return merge(merge(__snake_case	,	__snake_case      )	,	__snake_case      )





def 					lowercase_ (    __snake_case     :							Node | None	,	__snake_case     :							int      )     -> Node | None:





				'''simple docstring'''


				snake_case__      :List[str]         =   split(__snake_case	,	value - 1      )
				snake_case__      :str         =   split(__snake_case	,	__snake_case      )
				return merge(__snake_case	,	__snake_case      )





def 					lowercase_ (    __snake_case     :							Node | None      )     -> None:





				'''simple docstring'''


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





def 					lowercase_ (    __snake_case     :							Node | None	,	__snake_case     :							str      )     -> Node | None:





				'''simple docstring'''


				for arg in args.split():
								if arg[0] == "+":
												snake_case__      :Optional[Any]         =   insert(__snake_case	,	int(arg[1:]      )      )

								elif arg[0] == "-":
												snake_case__      :List[str]         =   erase(__snake_case	,	int(arg[1:]      )      )

								else:
												print("Unknown command"      )

				return root





def 					lowercase_ (    )     -> None:





				'''simple docstring'''


				snake_case__      :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. "      )

				snake_case__      :List[Any]         =   input()
				while args != "q":
								snake_case__      :List[str]         =   interact_treap(__snake_case	,	__snake_case      )
								print(__snake_case      )
								snake_case__      :int         =   input()

				print("good by!"      )


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()







def 					lowercase_ (    __snake_case     :							int      )     -> bool:





				'''simple docstring'''


				if p < 2:
								raise ValueError("p should not be less than 2!"      )
				elif p == 2:
								return True

				snake_case__      :List[str]         =   4
				snake_case__      :Optional[int]         =   (1 << p) - 1
				for _ in range(p - 2      ):
								snake_case__      :List[Any]         =   ((s * s) - 2) % m
				return s == 0


if __name__ == "__main__":
	print(lucas_lehmer_test(7))
	print(lucas_lehmer_test(1_1))