




from math import sqrt


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    number >= 0
	), "'number' must been an int and positive"

	snake_case_		    =     True

	# 0 and 1 are none primes.
	if number <= 1:
		snake_case_		    =     False

	for divisor in range(2     ,	int(round(sqrt(lowerCAmelCase__							)							)							) + 1							):
		# if 'number' divisible by 'divisor' then sets 'status'
		# of false and break up the loop.
		if number % divisor == 0:
			snake_case_		    =     False
			break

			 # precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'status' must been from type bool"

	return status


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n > 2), "'N' must been an int and > 2"

	# beginList: contains all natural numbers from 2 up to N
	snake_case_		    =     list(range(2     ,	n + 1							)							)

	snake_case_		    =     []  # this list will be returns.

	# actual sieve of erathostenes
	for i in range(len(lowerCAmelCase__							)							):
		for j in range(i + 1     ,	len(lowerCAmelCase__							)							):
			if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
				snake_case_		    =     0

				# filters actual prime numbers.
	snake_case_		    =     [x for x in begin_list if x != 0]

	# precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'ans' must been from type list"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n > 2), "'N' must been an int and > 2"

	snake_case_		    =     []

	# iterates over all numbers between 2 up to N+1
	# if a number is prime then appends to list 'ans'
	for number in range(2     ,	n + 1							):
		if is_prime(lowerCAmelCase__							):
			ans.append(lowerCAmelCase__							)

			 # precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'ans' must been from type list"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and number >= 0, "'number' must been an int and >= 0"

	snake_case_		    =     []  # this list will be returns of the function.

	# potential prime number factors.

	snake_case_		    =     2

	snake_case_		    =     number

	if number == 0 or number == 1:
		ans.append(lowerCAmelCase__							)

	# if 'number' not prime then builds the prime factorization of 'number'
	elif not is_prime(lowerCAmelCase__							):
		while quotient != 1:
			if is_prime(lowerCAmelCase__							) and (quotient % factor == 0):
				ans.append(lowerCAmelCase__							)
				quotient /= factor
			else:
				factor += 1

	else:
		ans.append(lowerCAmelCase__							)

	# precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'ans' must been from type list"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    number >= 0
	), "'number' bust been an int and >= 0"

	snake_case_		    =     0

	# prime factorization of 'number'
	snake_case_		    =     prime_factorization(lowerCAmelCase__							)

	snake_case_		    =     max(lowerCAmelCase__							)

	# precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'ans' must been from type int"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    number >= 0
	), "'number' bust been an int and >= 0"

	snake_case_		    =     0

	# prime factorization of 'number'
	snake_case_		    =     prime_factorization(lowerCAmelCase__							)

	snake_case_		    =     min(lowerCAmelCase__							)

	# precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'ans' must been from type int"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'number' must been an int"
	assert isinstance(number % 2 == 0     ,	lowerCAmelCase__							), "compare bust been from type bool"

	return number % 2 == 0


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							), "'number' must been an int"
	assert isinstance(number % 2 != 0     ,	lowerCAmelCase__							), "compare bust been from type bool"

	return number % 2 != 0


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (number > 2) and is_even(lowerCAmelCase__							)
	), "'number' must been an int, even and > 2"

	snake_case_		    =     []  # this list will returned

	# creates a list of prime numbers between 2 up to 'number'
	snake_case_		    =     get_prime_numbers(lowerCAmelCase__							)
	snake_case_		    =     len(lowerCAmelCase__							)

	# run variable for while-loops.
	snake_case_		    =     0
	snake_case_		    =     None

	# exit variable. for break up the loops
	snake_case_		    =     True

	while i < len_pn and loop:
		snake_case_		    =     i + 1

		while j < len_pn and loop:
			if prime_numbers[i] + prime_numbers[j] == number:
				snake_case_		    =     False
				ans.append(prime_numbers[i]							)
				ans.append(prime_numbers[j]							)

			j += 1

		i += 1

	# precondition
	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (len(lowerCAmelCase__							) == 2)
	    and (ans[0] + ans[1] == number)
	    and is_prime(ans[0]							)
	    and is_prime(ans[1]							)
	), "'ans' must contains two primes. And sum of elements must been eq 'number'"

	return ans


def 						lowerCamelCase__    (		_A     ,	_A							):







	'''simple docstring'''





	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (numbera >= 0)
	    and (numbera >= 0)
	), "'number1' and 'number2' must been positive integer."

	snake_case_		    =     0

	while numbera != 0:
		snake_case_		    =     numbera % numbera
		snake_case_		    =     numbera
		snake_case_		    =     rest

	# precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    numbera >= 0
	), "'number' must been from type int and positive"

	return numbera


def 						lowerCamelCase__    (		_A     ,	_A							):







	'''simple docstring'''





	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (numbera >= 1)
	    and (numbera >= 1)
	), "'number1' and 'number2' must been positive integer."

	snake_case_		    =     1  # actual answer that will be return.

	# for kgV (x,1)
	if numbera > 1 and numbera > 1:
		# builds the prime factorization of 'number1' and 'number2'
		snake_case_		    =     prime_factorization(lowerCAmelCase__							)
		snake_case_		    =     prime_factorization(lowerCAmelCase__							)

	elif numbera == 1 or numbera == 1:
		snake_case_		    =     []
		snake_case_		    =     []
		snake_case_		    =     max(lowerCAmelCase__     ,	lowerCAmelCase__							)

	snake_case_		    =     0
	snake_case_		    =     0

	snake_case_		    =     []  # captured numbers int both 'primeFac1' and 'primeFac2'

	# iterates through primeFac1
	for n in prime_fac_a:
		if n not in done:
			if n in prime_fac_a:
				snake_case_		    =     prime_fac_a.count(lowerCAmelCase__							)
				snake_case_		    =     prime_fac_a.count(lowerCAmelCase__							)

				for _ in range(max(lowerCAmelCase__     ,	lowerCAmelCase__							)							):
					ans *= n

			else:
				snake_case_		    =     prime_fac_a.count(lowerCAmelCase__							)

				for _ in range(lowerCAmelCase__							):
					ans *= n

			done.append(lowerCAmelCase__							)

			 # iterates through primeFac2
	for n in prime_fac_a:
		if n not in done:
			snake_case_		    =     prime_fac_a.count(lowerCAmelCase__							)

			for _ in range(lowerCAmelCase__							):
				ans *= n

			done.append(lowerCAmelCase__							)

			 # precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    ans >= 0
	), "'ans' must been from type int and positive"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n >= 0), "'number' must been a positive int"

	snake_case_		    =     0
	snake_case_		    =     2  # this variable holds the answer

	while index < n:
		index += 1

		ans += 1  # counts to the next number

		# if ans not prime then
		# runs to the next prime number.
		while not is_prime(lowerCAmelCase__							):
			ans += 1

			 # precondition
	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and is_prime(
	    lowerCAmelCase__							), "'ans' must been a prime number and from type int"

	return ans


def 						lowerCamelCase__    (		_A     ,	_A							):







	'''simple docstring'''





	assert (
	    is_prime(lowerCAmelCase__							) and is_prime(lowerCAmelCase__							) and (p_number_a < p_number_a)
	), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"

	snake_case_		    =     p_number_a + 1  # jump to the next number

	snake_case_		    =     []  # this list will be returns.

	# if number is not prime then
	# fetch the next prime number.
	while not is_prime(lowerCAmelCase__							):
		number += 1

	while number < p_number_a:
		ans.append(lowerCAmelCase__							)

		number += 1

		# fetch the next prime number.
		while not is_prime(lowerCAmelCase__							):
			number += 1

			 # precondition
	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and ans[0] != p_number_a
	    and ans[len(lowerCAmelCase__							) - 1] != p_number_a
	), "'ans' must been a list without the arguments"

	# 'ans' contains not 'pNumber1' and 'pNumber2' !
	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n >= 1), "'n' must been int and >= 1"

	snake_case_		    =     []  # will be returned.

	for divisor in range(1     ,	n + 1							):
		if n % divisor == 0:
			ans.append(lowerCAmelCase__							)

			 # precondition
	assert ans[0] == 1 and ans[len(lowerCAmelCase__							) - 1] == n, "Error in function getDivisiors(...)"

	return ans


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (
	    number > 1
	), "'number' must been an int and >= 1"

	snake_case_		    =     get_divisors(lowerCAmelCase__							)

	# precondition
	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (divisors[0] == 1)
	    and (divisors[len(lowerCAmelCase__							) - 1] == number)
	), "Error in help-function getDivisiors(...)"

	# summed all divisors up to 'number' (exclusive), hence [:-1]
	return sum(divisors[:-1]							) == number


def 						lowerCamelCase__    (		_A     ,	_A							):







	'''simple docstring'''





	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (denominator != 0)
	), "The arguments must been from type int and 'denominator' != 0"

	# build the greatest common divisor of numerator and denominator.
	snake_case_		    =     gcd(abs(lowerCAmelCase__							)     ,	abs(lowerCAmelCase__							)							)

	# precondition
	assert (
	    isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							)
	    and (numerator % gcd_of_fraction == 0)
	    and (denominator % gcd_of_fraction == 0)
	), "Error in function gcd(...,...)"

	return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)


def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n >= 0), "'n' must been a int and >= 0"

	snake_case_		    =     1  # this will be return.

	for factor in range(1     ,	n + 1							):
		ans *= factor

	return ans






def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	assert isinstance(lowerCAmelCase__     ,	lowerCAmelCase__							) and (n >= 0), "'n' must been an int and >= 0"

	snake_case_		    =     0
	snake_case_		    =     1
	snake_case_		    =     1  # this will be return

	for _ in range(n - 1							):
		snake_case_		    =     ans
		ans += fiba
		snake_case_		    =     tmp

	return ans


from __future__ import annotations

import math
import random
from typing import Any



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  list[Any]						=  []
    __a :  int						=  0
    __a :  int						=  0
   def       lowerCAmelCase			(self :					Optional[int]   ):
    return self.head == self.tail
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					Any   ):
    self.data.append(snake_case_   )
    __a :  str						=  self.tail + 1
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  int						=  self.data[self.head]
    __a :  Union[str, Any]						=  self.head + 1
    return ret
   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    return self.tail - self.head







   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    print(self.data   )
    print('''**************'''   )
    print(self.data[self.head : self.tail]   )





class 		UpperCamelCase__  :
   def __init__(self :					List[str]					,				snake_case_ :					Any   ):
    __a :  List[str]						=  data
    __a :  MyNode | None						=  None
    __a :  MyNode | None						=  None
    __a :  int						=  1
   def       lowerCAmelCase			(self :					int   ):
    return self.data
   def       lowerCAmelCase			(self :					Dict   ):
    return self.left
   def       lowerCAmelCase			(self :					int   ):
    return self.right
   def       lowerCAmelCase			(self :					int   ):
    return self.height
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Any   ):
    __a :  Tuple						=  data
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					MyNode | None   ):
    __a :  Any						=  node
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					MyNode | None   ):
    __a :  List[str]						=  node







   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					int   ):
    __a :  Union[str, Any]						=  height





def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ):
 if node is None:
  return 0
 return node.get_height()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ,   lowerCAmelCase__							:				int  ):
 if a > b:
  return a
 return b




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''left rotation node:'''  ,   node.get_data()  )
 __a :  str						=  node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()  )
 ret.set_right(lowerCAmelCase__  )
 __a :  List[Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''right rotation node:'''  ,   node.get_data()  )
 __a :  List[Any]						=  node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()  )
 ret.set_left(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  List[str]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Union[str, Any]						=  node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCAmelCase__  )  )
 return right_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Optional[int]						=  node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCAmelCase__  )  )
 return left_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ,   lowerCAmelCase__							:				Any  ):
 if node is None:
  return MyNode(lowerCAmelCase__  )
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()  ,   lowerCAmelCase__  )  )
  if (
      get_height(node.get_left()  ) - get_height(node.get_right()  ) == 2
  ):  # an unbalance detected
   __a :  Tuple						=  node.get_left()
   assert left_child is not None
   if (
       data < left_child.get_data()
   ):  # new node is the left child of the left child
    __a :  str						=  right_rotation(lowerCAmelCase__  )
   else:
    __a :  Dict						=  lr_rotation(lowerCAmelCase__  )
 else:
  node.set_right(insert_node(node.get_right()  ,   lowerCAmelCase__  )  )
  if get_height(node.get_right()  ) - get_height(node.get_left()  ) == 2:
   __a :  Dict						=  node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    __a :  str						=  rl_rotation(lowerCAmelCase__  )
   else:
    __a :  Tuple						=  left_rotation(lowerCAmelCase__  )
 __a :  Any						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 return node




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Union[str, Any]						=  root.get_right()
  if right_child is None:
   break
  __a :  str						=  right_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Optional[int]						=  root.get_left()
  if left_child is None:
   break
  __a :  int						=  left_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ,   lowerCAmelCase__							:				Any  ):
 __a :  Optional[Any]						=  root.get_left()
 __a :  List[str]						=  root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   __a :  str						=  get_left_most(lowerCAmelCase__  )
   root.set_data(lowerCAmelCase__  )
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
  elif left_child is not None:
   __a :  int						=  left_child
  elif right_child is not None:
   __a :  List[Any]						=  right_child
  else:
   return None
 elif root.get_data() > data:
  if left_child is None:
   print('''No such data'''  )
   return root
  else:
   root.set_left(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )

 if get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()  ) > get_height(right_child.get_left()  ):
   __a :  List[Any]						=  left_rotation(lowerCAmelCase__  )
  else:
   __a :  Union[str, Any]						=  rl_rotation(lowerCAmelCase__  )
 elif get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()  ) > get_height(left_child.get_right()  ):
   __a :  int						=  right_rotation(lowerCAmelCase__  )
  else:
   __a :  Tuple						=  lr_rotation(lowerCAmelCase__  )
 __a :  str						=  my_max(get_height(root.get_right()  )  ,   get_height(root.get_left()  )  ) + 1
 root.set_height(lowerCAmelCase__  )
 return root



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  MyNode | None						=  None
   def       lowerCAmelCase			(self :					List[Any]   ):
    return get_height(self.root   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    print('''insert:''' + str(snake_case_   )   )
    __a :  List[Any]						=  insert_node(self.root					,				snake_case_   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any   ):
    print('''delete:''' + str(snake_case_   )   )
    if self.root is None:
     print('''Tree is empty!'''   )
     return
    __a :  Union[str, Any]						=  del_node(self.root					,				snake_case_   )







   def __str__(self :					List[str]					,				):  # a level traversale, gives a more intuitive look on the tree
    __a :  Union[str, Any]						=  ''''''
    __a :  int						=  MyQueue()
    q.push(self.root   )
    __a :  List[str]						=  self.get_height()
    if layer == 0:
     return output
    __a :  List[Any]						=  0
    while not q.is_empty():
     __a :  List[str]						=  q.pop()
     __a :  Optional[int]						=  ''' ''' * int(math.pow(2					,				layer - 1   )   )
     output += space
     if node is None:
      output += "*"
      q.push(snake_case_   )
      q.push(snake_case_   )
     else:
      output += str(node.get_data()   )
      q.push(node.get_left()   )
      q.push(node.get_right()   )
     output += space
     __a :  int						=  cnt + 1
     for i in range(1_0_0   ):
      if cnt == math.pow(2					,				snake_case_   ) - 1:
       __a :  str						=  layer - 1
       if layer == 0:
        output += "\n*************************************"
        return output
       output += "\n"
       break
    output += "\n*************************************"
    return output





def    __UpperCamelCase     (				):
 import doctest

 doctest.testmod()


if __name__ == "__main__":
      _test()
      lowercase__       =AVLtree()
      lowercase__       =list(range(10))
      random.shuffle(lst)
      for i in lst:
            t.insert(i)
            print(str(t))
      random.shuffle(lst)
      for i in lst:
            t.del_node(i)
            print(str(t))
