






from __future__ import annotations

import math
import random
from typing import Any




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self     )			->   None:






            '''simple docstring'''





            __snake_case      :list[Any] 							=    []
            __snake_case      :int 							=    0
            __snake_case      :int 							=    0



       def        __lowercase    (				self     )			->   bool:






            '''simple docstring'''





            return self.head == self.tail



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            self.data.append(a__     )
            __snake_case      :Dict 							=    self.tail + 1



       def        __lowercase    (				self     )			->   Any:






            '''simple docstring'''





            __snake_case      :Tuple 							=    self.data[self.head]
            __snake_case      :Dict 							=    self.head + 1
            return ret



       def        __lowercase    (				self     )			->   int:






            '''simple docstring'''





            return self.tail - self.head



       def        __lowercase    (				self     )			->   None:






            '''simple docstring'''





            print(self.data     )
            print("""**************"""     )
            print(self.data[self.head : self.tail]     )




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self      ,    a__     )			->   None:






            '''simple docstring'''





            __snake_case      :int 							=    data
            __snake_case      :MyNode | None 							=    None
            __snake_case      :MyNode | None 							=    None
            __snake_case      :int 							=    1



       def        __lowercase    (				self     )			->   Any:






            '''simple docstring'''





            return self.data



       def        __lowercase    (				self     )			->   MyNode | None:






            '''simple docstring'''





            return self.left



       def        __lowercase    (				self     )			->   MyNode | None:






            '''simple docstring'''





            return self.right



       def        __lowercase    (				self     )			->   int:






            '''simple docstring'''





            return self.height



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            __snake_case      :str 							=    data



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            __snake_case      :int 							=    node



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            __snake_case      :Dict 							=    node



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            __snake_case      :Dict 							=    height






def 	UpperCamelCase	(							snake_case__  : MyNode | None	):




     '''simple docstring'''






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






def 	UpperCamelCase	(							snake_case__  : int						,snake_case__  : int	):




     '''simple docstring'''






     if a > b:
          return a
     return b






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     print("""left rotation node:"""						,node.get_data()	)
     __snake_case      :Any 							=    node.get_left()
     assert ret is not None
     node.set_left(ret.get_right()	)
     ret.set_right(snake_case__	)
     __snake_case      :Tuple 							=    my_max(get_height(node.get_right()	)						,get_height(node.get_left()	)	) + 1
     node.set_height(snake_case__	)
     __snake_case      :List[Any] 							=    my_max(get_height(ret.get_right()	)						,get_height(ret.get_left()	)	) + 1
     ret.set_height(snake_case__	)
     return ret






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     print("""right rotation node:"""						,node.get_data()	)
     __snake_case      :str 							=    node.get_right()
     assert ret is not None
     node.set_right(ret.get_left()	)
     ret.set_left(snake_case__	)
     __snake_case      :Union[str, Any] 							=    my_max(get_height(node.get_right()	)						,get_height(node.get_left()	)	) + 1
     node.set_height(snake_case__	)
     __snake_case      :str 							=    my_max(get_height(ret.get_right()	)						,get_height(ret.get_left()	)	) + 1
     ret.set_height(snake_case__	)
     return ret






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     __snake_case      :str 							=    node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(snake_case__	)	)
     return right_rotation(snake_case__	)






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     __snake_case      :str 							=    node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(snake_case__	)	)
     return left_rotation(snake_case__	)






def 	UpperCamelCase	(							snake_case__  : MyNode | None						,snake_case__  : Any	):




     '''simple docstring'''






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






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     while True:
          __snake_case      :List[str] 							=    root.get_right()
          if right_child is None:
               break
          __snake_case      :Any 							=    right_child
     return root.get_data()






def 	UpperCamelCase	(							snake_case__  : MyNode	):




     '''simple docstring'''






     while True:
          __snake_case      :List[str] 							=    root.get_left()
          if left_child is None:
               break
          __snake_case      :str 							=    left_child
     return root.get_data()






def 	UpperCamelCase	(							snake_case__  : MyNode						,snake_case__  : Any	):




     '''simple docstring'''






     __snake_case      :Tuple 							=    root.get_left()
     __snake_case      :Optional[int] 							=    root.get_right()
     if root.get_data() == data:
          if left_child is not None and right_child is not None:
               __snake_case      :int 							=    get_left_most(snake_case__	)
               root.set_data(snake_case__	)
               root.set_right(del_node(snake_case__						,snake_case__	)	)
          elif left_child is not None:
               __snake_case      :List[str] 							=    left_child
          elif right_child is not None:
               __snake_case      :Union[str, 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(snake_case__						,snake_case__	)	)
     else:  # root.get_data() < data
          if right_child is None:
               return root
          else:
               root.set_right(del_node(snake_case__						,snake_case__	)	)

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




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self     )			->   None:






            '''simple docstring'''





            __snake_case      :MyNode | None 							=    None



       def        __lowercase    (				self     )			->   int:






            '''simple docstring'''





            return get_height(self.root     )



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            print("""insert:""" + str(a__     )     )
            __snake_case      :Union[str, Any] 							=    insert_node(self.root      ,    a__     )



       def        __lowercase    (				self      ,    a__     )			->   None:






            '''simple docstring'''





            print("""delete:""" + str(a__     )     )
            if self.root is None:
                 print("""Tree is empty!"""     )
                 return
            __snake_case      :str 							=    del_node(self.root      ,    a__     )



       def __str__(				self      ,    )			->   str:  # a level traversale, gives a more intuitive look on the tree






            '''simple docstring'''





            __snake_case      :List[str] 							=    """"""
            __snake_case      :List[str] 							=    MyQueue()
            q.push(self.root     )
            __snake_case      :int 							=    self.get_height()
            if layer == 0:
                 return output
            __snake_case      :Optional[Any] 							=    0
            while not q.is_empty():
                 __snake_case      :str 							=    q.pop()
                 __snake_case      :Tuple 							=    """ """ * int(math.pow(2      ,    layer - 1     )     )
                 output += space
                 if node is None:
                      output += "*"
                      q.push(a__     )
                      q.push(a__     )
                 else:
                      output += str(node.get_data()     )
                      q.push(node.get_left()     )
                      q.push(node.get_right()     )
                 output += space
                 __snake_case      :str 							=    cnt + 1
                 for i in range(1_00     ):
                      if cnt == math.pow(2      ,    a__     ) - 1:
                           __snake_case      :Union[str, Any] 							=    layer - 1
                           if layer == 0:
                                output += "\n*************************************"
                                return output
                           output += "\n"
                           break
            output += "\n*************************************"
            return output






def 	UpperCamelCase	(							):




     '''simple docstring'''






     import doctest

     doctest.testmod()


if __name__ == "__main__":
     _test()
     lowerCamelCase__       		=  AVLtree()
     lowerCamelCase__       		=  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 	UpperCamelCase	(							snake_case__  : int	):




     '''simple docstring'''






     __snake_case      :List[Any] 							=    0
     while num > 0:
          digit_sum += num % 10
          num //= 10
     return digit_sum






def 	UpperCamelCase	(							snake_case__  : int = 100	):




     '''simple docstring'''






     __snake_case      :Tuple 							=    1
     __snake_case      :Dict 							=    2

     for i in range(2						,max_n + 1	):
          __snake_case      :Optional[int] 							=    pre_numerator
          __snake_case      :List[Any] 							=    2 * i // 3 if i % 3 == 0 else 1
          __snake_case      :Dict 							=    cur_numerator
          __snake_case      :Optional[Any] 							=    e_cont * pre_numerator + temp

     return sum_digits(snake_case__	)


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


