






from __future__ import annotations

import math
import random
from typing import Any
class 							A_    :






 '''simple docstring'''




 def __init__(	self) ->		None:

     """simple docstring"""



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


 def  snake_case__				(	self) ->		bool:

     """simple docstring"""



     return self.head == self.tail


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     self.data.append(_A)
     _UpperCAmelCase				:      List[Any]			  =				self.tail + 1


 def  snake_case__				(	self) ->		Any:

     """simple docstring"""



     _UpperCAmelCase				:      Optional[Any]			  =				self.data[self.head]
     _UpperCAmelCase				:      Tuple			  =				self.head + 1
     return ret


 def  snake_case__				(	self) ->		int:

     """simple docstring"""



     return self.tail - self.head


 def  snake_case__				(	self) ->		None:

     """simple docstring"""



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



class 							A_    :






 '''simple docstring'''




 def __init__(	self							,  _A) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      Optional[int]			  =				data
     _UpperCAmelCase				:      MyNode | None			  =				None
     _UpperCAmelCase				:      MyNode | None			  =				None
     _UpperCAmelCase				:      int			  =				1


 def  snake_case__				(	self) ->		Any:

     """simple docstring"""



     return self.data


 def  snake_case__				(	self) ->		MyNode | None:

     """simple docstring"""



     return self.left


 def  snake_case__				(	self) ->		MyNode | None:

     """simple docstring"""



     return self.right


 def  snake_case__				(	self) ->		int:

     """simple docstring"""



     return self.height


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      Union[str, Any]			  =				data


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      Any			  =				node


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      Optional[Any]			  =				node


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      str			  =				height



def      _lowerCamelCase	(						__A    :							MyNode | None )      ->					int:
    if node is None:
        return 0
    return node.get_height()

def      _lowerCamelCase	(						__A    :							int		,		__A    :							int )      ->					int:
    if a > b:
        return a
    return b

def      _lowerCamelCase	(						__A    :							MyNode )      ->					MyNode:
    print('''left rotation node:'''		,		node.get_data() )
    _UpperCAmelCase				:      Dict			  =				node.get_left()
    assert ret is not None
    node.set_left(ret.get_right() )
    ret.set_right(__A )
    _UpperCAmelCase				:      List[Any]			  =				my_max(get_height(node.get_right() )		,		get_height(node.get_left() ) ) + 1
    node.set_height(__A )
    _UpperCAmelCase				:      str			  =				my_max(get_height(ret.get_right() )		,		get_height(ret.get_left() ) ) + 1
    ret.set_height(__A )
    return ret

def      _lowerCamelCase	(						__A    :							MyNode )      ->					MyNode:
    print('''right rotation node:'''		,		node.get_data() )
    _UpperCAmelCase				:      Tuple			  =				node.get_right()
    assert ret is not None
    node.set_right(ret.get_left() )
    ret.set_left(__A )
    _UpperCAmelCase				:      str			  =				my_max(get_height(node.get_right() )		,		get_height(node.get_left() ) ) + 1
    node.set_height(__A )
    _UpperCAmelCase				:      str			  =				my_max(get_height(ret.get_right() )		,		get_height(ret.get_left() ) ) + 1
    ret.set_height(__A )
    return ret

def      _lowerCamelCase	(						__A    :							MyNode )      ->					MyNode:
    _UpperCAmelCase				:      Union[str, Any]			  =				node.get_left()
    assert left_child is not None
    node.set_left(left_rotation(__A ) )
    return right_rotation(__A )

def      _lowerCamelCase	(						__A    :							MyNode )      ->					MyNode:
    _UpperCAmelCase				:      int			  =				node.get_right()
    assert right_child is not None
    node.set_right(right_rotation(__A ) )
    return left_rotation(__A )

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

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

def      _lowerCamelCase	(						__A    :							MyNode )      ->					Any:
    while True:
        _UpperCAmelCase				:      str			  =				root.get_left()
        if left_child is None:
            break
        _UpperCAmelCase				:      str			  =				left_child
    return root.get_data()

def      _lowerCamelCase	(						__A    :							MyNode		,		__A    :							Any )      ->					MyNode | None:
    _UpperCAmelCase				:      Tuple			  =				root.get_left()
    _UpperCAmelCase				:      str			  =				root.get_right()
    if root.get_data() == data:
        if left_child is not None and right_child is not None:
            _UpperCAmelCase				:      Optional[Any]			  =				get_left_most(__A )
            root.set_data(__A )
            root.set_right(del_node(__A		,		__A ) )
        elif left_child is not None:
            _UpperCAmelCase				:      Tuple			  =				left_child
        elif right_child is not None:
            _UpperCAmelCase				:      Tuple			  =				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(__A		,		__A ) )
    else:  # root.get_data() < data
        if right_child is None:
            return root
        else:
            root.set_right(del_node(__A		,		__A ) )

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






 '''simple docstring'''




 def __init__(	self) ->		None:

     """simple docstring"""



     _UpperCAmelCase				:      MyNode | None			  =				None


 def  snake_case__				(	self) ->		int:

     """simple docstring"""



     return get_height(self.root)


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     print('''insert:''' + str(_A))
     _UpperCAmelCase				:      int			  =				insert_node(self.root							,  _A)


 def  snake_case__				(	self							,  _A) ->		None:

     """simple docstring"""



     print('''delete:''' + str(_A))
     if self.root is None:
         print('''Tree is empty!''')
         return
     _UpperCAmelCase				:      Union[str, Any]			  =				del_node(self.root							,  _A)


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

     """simple docstring"""



     _UpperCAmelCase				:      int			  =				''''''
     _UpperCAmelCase				:      Dict			  =				MyQueue()
     q.push(self.root)
     _UpperCAmelCase				:      Union[str, Any]			  =				self.get_height()
     if layer == 0:
         return output
     _UpperCAmelCase				:      Dict			  =				0
     while not q.is_empty():
         _UpperCAmelCase				:      Union[str, Any]			  =				q.pop()
         _UpperCAmelCase				:      Dict			  =				''' ''' * 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
         _UpperCAmelCase				:      Tuple			  =				cnt + 1
         for i in range(100):
             if cnt == math.pow(2							,  _A) - 1:
                 _UpperCAmelCase				:      Optional[Any]			  =				layer - 1
                 if layer == 0:
                     output += "\n*************************************"
                     return output
                 output += "\n"
                 break
     output += "\n*************************************"
     return output



def      _lowerCamelCase	(						)      ->					None:
    import doctest

    doctest.testmod()


if __name__ == "__main__":
       _test()
       SCREAMING_SNAKE_CASE 							=						AVLtree()
       SCREAMING_SNAKE_CASE 							=						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))












from math import pow, sqrt

def      _lowerCamelCase	(						*__A    :							float )      ->					bool:
    _UpperCAmelCase				:      str			  =				len(__A ) > 0 and all(value > 0.0 for value in values )
    return result

def      _lowerCamelCase	(						__A    :							float		,		__A    :							float )      ->					float | ValueError:
    return (
        round(sqrt(molar_mass_a / molar_mass_a )		,		6 )
        if validate(__A		,		__A )
        else ValueError('''Input Error: Molar mass values must greater than 0.''' )
    )

def      _lowerCamelCase	(						__A    :							float		,		__A    :							float		,		__A    :							float )      ->					float | ValueError:
    return (
        round(effusion_rate * sqrt(molar_mass_a / molar_mass_a )		,		6 )
        if validate(__A		,		__A		,		__A )
        else ValueError(
            '''Input Error: Molar mass and effusion rate values must greater than 0.''' )
    )

def      _lowerCamelCase	(						__A    :							float		,		__A    :							float		,		__A    :							float )      ->					float | ValueError:
    return (
        round(effusion_rate / sqrt(molar_mass_a / molar_mass_a )		,		6 )
        if validate(__A		,		__A		,		__A )
        else ValueError(
            '''Input Error: Molar mass and effusion rate values must greater than 0.''' )
    )

def      _lowerCamelCase	(						__A    :							float		,		__A    :							float		,		__A    :							float )      ->					float | ValueError:
    return (
        round(molar_mass / pow(effusion_rate_a / effusion_rate_a		,		2 )		,		6 )
        if validate(__A		,		__A		,		__A )
        else ValueError(
            '''Input Error: Molar mass and effusion rate values must greater than 0.''' )
    )


def      _lowerCamelCase	(						__A    :							float		,		__A    :							float		,		__A    :							float )      ->					float | ValueError:
    return (
        round(pow(effusion_rate_a / effusion_rate_a		,		2 ) / molar_mass		,		6 )
        if validate(__A		,		__A		,		__A )
        else ValueError(
            '''Input Error: Molar mass and effusion rate values must greater than 0.''' )
    )




