




from __future__ import annotations

import math
import random
from typing import Any




class 					snake_case__							:
    """simple docstring"""



    def __init__(   self       :  List[str]							)      ->  Union[str, Any]:
       a					=    []
       a					=    0
       a					=    0





    def 							__UpperCAmelCase							(   self       :  Union[str, Any]							)      ->  Any:
       return self.head == self.tail





    def 							__UpperCAmelCase							(   self       :  Any      ,   __lowerCamelCase       :  str							)      ->  List[Any]:
       self.data.append(__lowerCamelCase							)
       a					=    self.tail + 1





    def 							__UpperCAmelCase							(   self       :  Union[str, Any]							)      ->  str:
       a					=    self.data[self.head]
       a					=    self.head + 1
       return ret





    def 							__UpperCAmelCase							(   self       :  str							)      ->  Dict:
       return self.tail - self.head





    def 							__UpperCAmelCase							(   self       :  Union[str, Any]							)      ->  List[str]:
       print(self.data							)
       print("**************"							)
       print(self.data[self.head : self.tail]							)




class 					snake_case__							:
    """simple docstring"""



    def __init__(   self       :  Dict      ,   __lowerCamelCase       :  Dict							)      ->  Optional[Any]:
       a					=    data
       a					=    None
       a					=    None
       a					=    1





    def 							__UpperCAmelCase							(   self       :  Union[str, Any]							)      ->  str:
       return self.data





    def 							__UpperCAmelCase							(   self       :  Optional[Any]							)      ->  Union[str, Any]:
       return self.left





    def 							__UpperCAmelCase							(   self       :  Any							)      ->  Dict:
       return self.right





    def 							__UpperCAmelCase							(   self       :  str							)      ->  str:
       return self.height





    def 							__UpperCAmelCase							(   self       :  int      ,   __lowerCamelCase       :  Optional[Any]							)      ->  Tuple:
       a					=    data





    def 							__UpperCAmelCase							(   self       :  List[Any]      ,   __lowerCamelCase       :  List[str]							)      ->  Any:
       a					=    node





    def 							__UpperCAmelCase							(   self       :  List[str]      ,   __lowerCamelCase       :  Tuple							)      ->  Dict:
       a					=    node





    def 							__UpperCAmelCase							(   self       :  List[str]      ,   __lowerCamelCase       :  Dict							)      ->  Any:
       a					=    height




def     __magic_name__       (				A	:      Optional[int]     ):






   '''simple docstring'''







   if node is None:
      return 0
   return node.get_height()




def     __magic_name__       (				A	:      int,						A	:      Any     ):






   '''simple docstring'''







   if a > b:
      return a
   return b




def     __magic_name__       (				A	:      Tuple     ):






   '''simple docstring'''







   print("left rotation node:",						node.get_data()     )
   a					=    node.get_left()
   assert ret is not None
   node.set_left(ret.get_right()     )
   ret.set_right(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(node.get_right()     ),						get_height(node.get_left()     )     ) + 1
   node.set_height(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(ret.get_right()     ),						get_height(ret.get_left()     )     ) + 1
   ret.set_height(__SCREAMING_SNAKE_CASE     )
   return ret




def     __magic_name__       (				A	:      Any     ):






   '''simple docstring'''







   print("right rotation node:",						node.get_data()     )
   a					=    node.get_right()
   assert ret is not None
   node.set_right(ret.get_left()     )
   ret.set_left(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(node.get_right()     ),						get_height(node.get_left()     )     ) + 1
   node.set_height(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(ret.get_right()     ),						get_height(ret.get_left()     )     ) + 1
   ret.set_height(__SCREAMING_SNAKE_CASE     )
   return ret




def     __magic_name__       (				A	:      Optional[Any]     ):






   '''simple docstring'''







   a					=    node.get_left()
   assert left_child is not None
   node.set_left(left_rotation(__SCREAMING_SNAKE_CASE     )     )
   return right_rotation(__SCREAMING_SNAKE_CASE     )




def     __magic_name__       (				A	:      str     ):






   '''simple docstring'''







   a					=    node.get_right()
   assert right_child is not None
   node.set_right(right_rotation(__SCREAMING_SNAKE_CASE     )     )
   return left_rotation(__SCREAMING_SNAKE_CASE     )




def     __magic_name__       (				A	:      Union[str, Any],						A	:      Union[str, Any]     ):






   '''simple docstring'''







   if node is None:
      return MyNode(__SCREAMING_SNAKE_CASE     )
   if data < node.get_data():
      node.set_left(insert_node(node.get_left(),						__SCREAMING_SNAKE_CASE     )     )
      if (
          get_height(node.get_left()     ) - get_height(node.get_right()     ) == 2
      ):  # an unbalance detected
         a					=    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					=    right_rotation(__SCREAMING_SNAKE_CASE     )
         else:
            a					=    lr_rotation(__SCREAMING_SNAKE_CASE     )
   else:
      node.set_right(insert_node(node.get_right(),						__SCREAMING_SNAKE_CASE     )     )
      if get_height(node.get_right()     ) - get_height(node.get_left()     ) == 2:
         a					=    node.get_right()
         assert right_child is not None
         if data < right_child.get_data():
            a					=    rl_rotation(__SCREAMING_SNAKE_CASE     )
         else:
            a					=    left_rotation(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(node.get_right()     ),						get_height(node.get_left()     )     ) + 1
   node.set_height(__SCREAMING_SNAKE_CASE     )
   return node




def     __magic_name__       (				A	:      Union[str, Any]     ):






   '''simple docstring'''







   while True:
      a					=    root.get_right()
      if right_child is None:
         break
      a					=    right_child
   return root.get_data()




def     __magic_name__       (				A	:      int     ):






   '''simple docstring'''







   while True:
      a					=    root.get_left()
      if left_child is None:
         break
      a					=    left_child
   return root.get_data()




def     __magic_name__       (				A	:      str,						A	:      str     ):






   '''simple docstring'''







   a					=    root.get_left()
   a					=    root.get_right()
   if root.get_data() == data:
      if left_child is not None and right_child is not None:
         a					=    get_left_most(__SCREAMING_SNAKE_CASE     )
         root.set_data(__SCREAMING_SNAKE_CASE     )
         root.set_right(del_node(__SCREAMING_SNAKE_CASE,						__SCREAMING_SNAKE_CASE     )     )
      elif left_child is not None:
         a					=    left_child
      elif right_child is not None:
         a					=    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(__SCREAMING_SNAKE_CASE,						__SCREAMING_SNAKE_CASE     )     )
   else:  # root.get_data() < data
      if right_child is None:
         return root
      else:
         root.set_right(del_node(__SCREAMING_SNAKE_CASE,						__SCREAMING_SNAKE_CASE     )     )

   if get_height(__SCREAMING_SNAKE_CASE     ) - get_height(__SCREAMING_SNAKE_CASE     ) == 2:
      assert right_child is not None
      if get_height(right_child.get_right()     ) > get_height(right_child.get_left()     ):
         a					=    left_rotation(__SCREAMING_SNAKE_CASE     )
      else:
         a					=    rl_rotation(__SCREAMING_SNAKE_CASE     )
   elif get_height(__SCREAMING_SNAKE_CASE     ) - get_height(__SCREAMING_SNAKE_CASE     ) == -2:
      assert left_child is not None
      if get_height(left_child.get_left()     ) > get_height(left_child.get_right()     ):
         a					=    right_rotation(__SCREAMING_SNAKE_CASE     )
      else:
         a					=    lr_rotation(__SCREAMING_SNAKE_CASE     )
   a					=    my_max(get_height(root.get_right()     ),						get_height(root.get_left()     )     ) + 1
   root.set_height(__SCREAMING_SNAKE_CASE     )
   return root




class 					snake_case__							:
    """simple docstring"""



    def __init__(   self       :  Tuple							)      ->  Any:
       a					=    None





    def 							__UpperCAmelCase							(   self       :  Any							)      ->  List[Any]:
       return get_height(self.root							)





    def 							__UpperCAmelCase							(   self       :  Union[str, Any]      ,   __lowerCamelCase       :  List[str]							)      ->  List[Any]:
       print("insert:" + str(__lowerCamelCase							)							)
       a					=    insert_node(self.root      ,   __lowerCamelCase							)





    def 							__UpperCAmelCase							(   self       :  Optional[Any]      ,   __lowerCamelCase       :  Union[str, Any]							)      ->  List[Any]:
       print("delete:" + str(__lowerCamelCase							)							)
       if self.root is None:
          print("Tree is empty!"							)
          return
       a					=    del_node(self.root      ,   __lowerCamelCase							)





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




def     __magic_name__       (				):






   '''simple docstring'''







   import doctest

   doctest.testmod()


if __name__ == "__main__":
  _test()
  __lowerCAmelCase	:       Union[str, Any]     =	AVLtree()
  __lowerCAmelCase	:       List[Any]     =	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))












def     __magic_name__       (				A	:      int,						A	:      int,						A	:      int     ):






			'''simple docstring'''







			if exponent == 1:
						return base
			if exponent % 2 == 0:
						a					=    _modexpt(A,						exponent // 2,						A     ) % modulo_value
						return (x * x) % modulo_value
			else:
						return (base * _modexpt(A,						exponent - 1,						A     )) % modulo_value




def     __magic_name__       (				A	:      int = 1777,						A	:      int = 1855,						A	:      int = 8     ):






			'''simple docstring'''







			a					=    base
			for _ in range(1,						A     ):
						a					=    _modexpt(A,						A,						10**digits     )

			return result


if __name__ == "__main__":
		print(F'''{solution() = }''')






