





'''simple docstring'''




from __future__ import annotations

import math
import random
from typing import Any







class   A_	:




 def __init__(					self       :    List[Any]    ):
      _UpperCAmelCase     							=   []
      _UpperCAmelCase     							=   0
      _UpperCAmelCase     							=   0




 def      lowercase	(					self       :    Optional[Any]    ):
      return self.head == self.tail




 def      lowercase	(					self       :    Optional[int]	,			snake_case_       :    Dict    ):
      self.data.append(__UpperCamelCase    )
      _UpperCAmelCase     							=   self.tail + 1




 def      lowercase	(					self       :    Optional[Any]    ):
      _UpperCAmelCase     							=   self.data[self.head]
      _UpperCAmelCase     							=   self.head + 1
      return ret




 def      lowercase	(					self       :    List[Any]    ):
      return self.tail - self.head




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







class   A_	:




 def __init__(					self       :    List[Any]	,			snake_case_       :    str    ):
      _UpperCAmelCase     							=   data
      _UpperCAmelCase     							=   None
      _UpperCAmelCase     							=   None
      _UpperCAmelCase     							=   1




 def      lowercase	(					self       :    List[str]    ):
      return self.data




 def      lowercase	(					self       :    List[str]    ):
      return self.left




 def      lowercase	(					self       :    Dict    ):
      return self.right




 def      lowercase	(					self       :    Optional[Any]    ):
      return self.height




 def      lowercase	(					self       :    List[str]	,			snake_case_       :    Union[str, Any]    ):
      _UpperCAmelCase     							=   data




 def      lowercase	(					self       :    Union[str, Any]	,			snake_case_       :    Optional[int]    ):
      _UpperCAmelCase     							=   node




 def      lowercase	(					self       :    Union[str, Any]	,			snake_case_       :    Any    ):
      _UpperCAmelCase     							=   node




 def      lowercase	(					self       :    Dict	,			snake_case_       :    List[str]    ):
      _UpperCAmelCase     							=   height





def 	UpperCAmelCase_							(					__lowercase							:      MyNode | None       )		->       Optional[int]:


     '''simple docstring'''



     if node is None:
          return 0
     return node.get_height()
def 	UpperCAmelCase_							(					__lowercase							:      int			,     __lowercase							:      int       )		->       Union[str, Any]:


     '''simple docstring'''



     if a > b:
          return a
     return b
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       Tuple:


     '''simple docstring'''



     print("left rotation node:"			,     node.get_data()       )
     _UpperCAmelCase     							=   node.get_left()
     assert ret is not None
     node.set_left(ret.get_right()       )
     ret.set_right(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(node.get_right()       )			,     get_height(node.get_left()       )       ) + 1
     node.set_height(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(ret.get_right()       )			,     get_height(ret.get_left()       )       ) + 1
     ret.set_height(__SCREAMING_SNAKE_CASE       )
     return ret
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       str:


     '''simple docstring'''



     print("right rotation node:"			,     node.get_data()       )
     _UpperCAmelCase     							=   node.get_right()
     assert ret is not None
     node.set_right(ret.get_left()       )
     ret.set_left(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(node.get_right()       )			,     get_height(node.get_left()       )       ) + 1
     node.set_height(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(ret.get_right()       )			,     get_height(ret.get_left()       )       ) + 1
     ret.set_height(__SCREAMING_SNAKE_CASE       )
     return ret
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       Union[str, Any]:


     '''simple docstring'''



     _UpperCAmelCase     							=   node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(__SCREAMING_SNAKE_CASE       )       )
     return right_rotation(__SCREAMING_SNAKE_CASE       )
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       List[str]:


     '''simple docstring'''



     _UpperCAmelCase     							=   node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(__SCREAMING_SNAKE_CASE       )       )
     return left_rotation(__SCREAMING_SNAKE_CASE       )
def 	UpperCAmelCase_							(					__lowercase							:      MyNode | None			,     __lowercase							:      Any       )		->       Optional[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
               _UpperCAmelCase     							=   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
                    _UpperCAmelCase     							=   right_rotation(__SCREAMING_SNAKE_CASE       )
               else:
                    _UpperCAmelCase     							=   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:
               _UpperCAmelCase     							=   node.get_right()
               assert right_child is not None
               if data < right_child.get_data():
                    _UpperCAmelCase     							=   rl_rotation(__SCREAMING_SNAKE_CASE       )
               else:
                    _UpperCAmelCase     							=   left_rotation(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(node.get_right()       )			,     get_height(node.get_left()       )       ) + 1
     node.set_height(__SCREAMING_SNAKE_CASE       )
     return node
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       str:


     '''simple docstring'''



     while True:
          _UpperCAmelCase     							=   root.get_right()
          if right_child is None:
               break
          _UpperCAmelCase     							=   right_child
     return root.get_data()
def 	UpperCAmelCase_							(					__lowercase							:      MyNode       )		->       List[Any]:


     '''simple docstring'''



     while True:
          _UpperCAmelCase     							=   root.get_left()
          if left_child is None:
               break
          _UpperCAmelCase     							=   left_child
     return root.get_data()
def 	UpperCAmelCase_							(					__lowercase							:      MyNode			,     __lowercase							:      Any       )		->       Any:


     '''simple docstring'''



     _UpperCAmelCase     							=   root.get_left()
     _UpperCAmelCase     							=   root.get_right()
     if root.get_data() == data:
          if left_child is not None and right_child is not None:
               _UpperCAmelCase     							=   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:
               _UpperCAmelCase     							=   left_child
          elif right_child is not None:
               _UpperCAmelCase     							=   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()       ):
               _UpperCAmelCase     							=   left_rotation(__SCREAMING_SNAKE_CASE       )
          else:
               _UpperCAmelCase     							=   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()       ):
               _UpperCAmelCase     							=   right_rotation(__SCREAMING_SNAKE_CASE       )
          else:
               _UpperCAmelCase     							=   lr_rotation(__SCREAMING_SNAKE_CASE       )
     _UpperCAmelCase     							=   my_max(get_height(root.get_right()       )			,     get_height(root.get_left()       )       ) + 1
     root.set_height(__SCREAMING_SNAKE_CASE       )
     return root







class   A_	:




 def __init__(					self       :    Dict    ):
      _UpperCAmelCase     							=   None




 def      lowercase	(					self       :    Optional[int]    ):
      return get_height(self.root    )




 def      lowercase	(					self       :    Optional[int]	,			snake_case_       :    Any    ):
      print("insert:" + str(__UpperCamelCase    )    )
      _UpperCAmelCase     							=   insert_node(self.root	,			__UpperCamelCase    )




 def      lowercase	(					self       :    Any	,			snake_case_       :    Dict    ):
      print("delete:" + str(__UpperCamelCase    )    )
      if self.root is None:
           print("Tree is empty!"    )
           return
      _UpperCAmelCase     							=   del_node(self.root	,			__UpperCamelCase    )




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





def 	UpperCAmelCase_							(					)		->       int:


     '''simple docstring'''



     import doctest

     doctest.testmod()


if __name__ == "__main__":
  _test()
  __SCREAMING_SNAKE_CASE     :int       =				AVLtree()
  __SCREAMING_SNAKE_CASE     :Optional[int]       =				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))





"""simple docstring"""







__SCREAMING_SNAKE_CASE    	={}



def 			lowercase__(       __SCREAMING_SNAKE_CASE							:     int     ,			__SCREAMING_SNAKE_CASE							:     int     ,			__SCREAMING_SNAKE_CASE							:     int      ):

     # if we are absent twice, or late 3 consecutive days,
     # no further prize strings are possible
     if late == 3 or absent == 2:
          return 0

     # if we have no days left, and have not failed any other rules,
     # we have a prize string
     if days == 0:
          return 1

     # No easy solution, so now we need to do the recursive calculation

     # First, check if the combination is already in the cache, and
     # if yes, return the stored value from there since we already
     # know the number of possible prize strings from this point on
     lowercase_	:				Any													=	(days, absent, late)
     if key in cache:
          return cache[key]

     # now we calculate the three possible ways that can unfold from
     # this point on, depending on our attendance today

     # 1) if we are late (but not absent), the "absent" counter stays as
     # it is, but the "late" counter increases by one
     lowercase_	:				Optional[int]													=	_calculate(days - 1     ,			__SCREAMING_SNAKE_CASE     ,			late + 1      )

     # 2) if we are absent, the "absent" counter increases by 1, and the
     # "late" counter resets to 0
     lowercase_	:				Any													=	_calculate(days - 1     ,			absent + 1     ,			0      )

     # 3) if we are on time, this resets the "late" counter and keeps the
     # absent counter
     lowercase_	:				Dict													=	_calculate(days - 1     ,			__SCREAMING_SNAKE_CASE     ,			0      )

     lowercase_	:				str													=	state_late + state_absent + state_ontime

     lowercase_	:				Tuple													=	prizestrings
     return prizestrings



def 			lowercase__(       __SCREAMING_SNAKE_CASE							:     int = 30      ):
     return _calculate(__SCREAMING_SNAKE_CASE     ,			absent=0     ,			late=0      )


if __name__ == "__main__":
       print(solution())

