

'''simple docstring'''
from __future__ import annotations

import math
import random
from typing import Any







class 							A__    :





  def __init__(		self      :	Optional[int] )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =[]
       _SCREAMING_SNAKE_CASE							    =0
       _SCREAMING_SNAKE_CASE							    =0





  def 						A  (		self      :	Dict )	->    bool:





       '''simple docstring'''






       return self.head == self.tail





  def 						A  (		self      :	str							,					_a      :	Any )	->    None:





       '''simple docstring'''






       self.data.append(_a )
       _SCREAMING_SNAKE_CASE							    =self.tail + 1





  def 						A  (		self      :	List[str] )	->    Any:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =self.data[self.head]
       _SCREAMING_SNAKE_CASE							    =self.head + 1
       return ret





  def 						A  (		self      :	Optional[int] )	->    int:





       '''simple docstring'''






       return self.tail - self.head





  def 						A  (		self      :	int )	->    None:





       '''simple docstring'''






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







class 							A__    :





  def __init__(		self      :	Optional[Any]							,					_a      :	Any )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =data
       _SCREAMING_SNAKE_CASE							    =None
       _SCREAMING_SNAKE_CASE							    =None
       _SCREAMING_SNAKE_CASE							    =1





  def 						A  (		self      :	Tuple )	->    Any:





       '''simple docstring'''






       return self.data





  def 						A  (		self      :	Any )	->    MyNode | None:





       '''simple docstring'''






       return self.left





  def 						A  (		self      :	Dict )	->    MyNode | None:





       '''simple docstring'''






       return self.right





  def 						A  (		self      :	List[str] )	->    int:





       '''simple docstring'''






       return self.height





  def 						A  (		self      :	List[Any]							,					_a      :	Any )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =data





  def 						A  (		self      :	Dict							,					_a      :	MyNode | None )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =node





  def 						A  (		self      :	Optional[int]							,					_a      :	MyNode | None )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =node





  def 						A  (		self      :	Dict							,					_a      :	int )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =height


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode | None				)      ->			int:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     int							, _UpperCamelCase						:     int				)      ->			int:
     """simple docstring"""




     if a > b:
          return a
     return b


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			MyNode:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			MyNode:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			MyNode:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(_UpperCamelCase				)				)
     return right_rotation(_UpperCamelCase				)


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			MyNode:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(_UpperCamelCase				)				)
     return left_rotation(_UpperCamelCase				)


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode | None							, _UpperCamelCase						:     Any				)      ->			MyNode | None:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			Any:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode				)      ->			Any:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     MyNode							, _UpperCamelCase						:     Any				)      ->			MyNode | None:
     """simple docstring"""




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

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







class 							A__    :





  def __init__(		self      :	Union[str, Any] )	->    None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =None





  def 						A  (		self      :	str )	->    int:





       '''simple docstring'''






       return get_height(self.root )





  def 						A  (		self      :	Optional[int]							,					_a      :	Any )	->    None:





       '''simple docstring'''






       print('insert:' + str(_a ) )
       _SCREAMING_SNAKE_CASE							    =insert_node(self.root							,					_a )





  def 						A  (		self      :	Any							,					_a      :	Any )	->    None:





       '''simple docstring'''






       print('delete:' + str(_a ) )
       if self.root is None:
            print('Tree is empty!' )
            return
       _SCREAMING_SNAKE_CASE							    =del_node(self.root							,					_a )





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





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =''
       _SCREAMING_SNAKE_CASE							    =MyQueue()
       q.push(self.root )
       _SCREAMING_SNAKE_CASE							    =self.get_height()
       if layer == 0:
            return output
       _SCREAMING_SNAKE_CASE							    =0
       while not q.is_empty():
            _SCREAMING_SNAKE_CASE							    =q.pop()
            _SCREAMING_SNAKE_CASE							    =' ' * 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
            _SCREAMING_SNAKE_CASE							    =cnt + 1
            for i in range(100 ):
                 if cnt == math.pow(2							,					_a ) - 1:
                      _SCREAMING_SNAKE_CASE							    =layer - 1
                      if layer == 0:
                           output += "\n*************************************"
                           return output
                      output += "\n"
                      break
       output += "\n*************************************"
       return output


def        _lowerCAmelCase					(						)      ->			None:
     """simple docstring"""




     import doctest

     doctest.testmod()


if __name__ == "__main__":
     _test()
     lowerCamelCase :      Union[str, Any]					 =     AVLtree()
     lowerCamelCase :      Any					 =     list(range(1_0))
     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'''
from __future__ import annotations

import math


def        _lowerCAmelCase					(						_UpperCamelCase						:     int				)      ->			bool:
     """simple docstring"""




     if 1 < number < 4:
          # 2 and 3 are primes
          return True
     elif number < 2 or number % 2 == 0 or number % 3 == 0:
          # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
          return False

     # All primes number are in format of 6k +/- 1
     for i in range(5							, int(math.sqrt(_UpperCamelCase				) + 1				)							, 6				):
          if number % i == 0 or number % (i + 2) == 0:
               return False
     return True


def        _lowerCAmelCase					(						_UpperCamelCase						:     int				)      ->			list[int]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =str(_UpperCamelCase				)
     _SCREAMING_SNAKE_CASE							    =[n]
     for i in range(1							, len(_UpperCamelCase				)				):
          list_nums.append(int(str_num[i:]				)				)
          list_nums.append(int(str_num[:-i]				)				)
     return list_nums


def        _lowerCAmelCase					(						_UpperCamelCase						:     int				)      ->			bool:
     """simple docstring"""




     if len(str(_UpperCamelCase				)				) > 3:
          if not is_prime(int(str(_UpperCamelCase				)[-3:]				)				) or not is_prime(int(str(_UpperCamelCase				)[:3]				)				):
               return False
     return True


def        _lowerCAmelCase					(						_UpperCamelCase						:     int = 11				)      ->			list[int]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =[]
     _SCREAMING_SNAKE_CASE							    =13
     while len(_UpperCamelCase				) != count:
          if validate(_UpperCamelCase				):
               _SCREAMING_SNAKE_CASE							    =list_truncated_nums(_UpperCamelCase				)
               if all(is_prime(_UpperCamelCase				) for i in list_nums				):
                    list_truncated_primes.append(_UpperCamelCase				)
          num += 2
     return list_truncated_primes


def        _lowerCAmelCase					(						)      ->			int:
     """simple docstring"""




     return sum(compute_truncated_primes(11				)				)


if __name__ == "__main__":
     print(f'''{sum(compute_truncated_primes(1_1)) = }''')
