"""simple docstring"""





from __future__ import annotations

import math
import random
from typing import Any


class   UpperCAmelCase_			:


      def __init__(     self							) ->      None:
             lowercase__    :	list[Any]     					=			[]
             lowercase__    :	int     					=			0
             lowercase__    :	int     					=			0


      def 	_UpperCAmelCase (     self							) ->      bool:
             return self.head == self.tail


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             self.data.append(__a							)
             lowercase__    :	Optional[Any]     					=			self.tail + 1


      def 	_UpperCAmelCase (     self							) ->      Any:
             lowercase__    :	Optional[int]     					=			self.data[self.head]
             lowercase__    :	Union[str, Any]     					=			self.head + 1
             return ret


      def 	_UpperCAmelCase (     self							) ->      int:
             return self.tail - self.head


      def 	_UpperCAmelCase (     self							) ->      None:
             print(self.data							)
             print('**************'							)
             print(self.data[self.head : self.tail]							)





class   UpperCAmelCase_			:


      def __init__(     self	,    a							) ->      None:
             lowercase__    :	Tuple     					=			data
             lowercase__    :	MyNode | None     					=			None
             lowercase__    :	MyNode | None     					=			None
             lowercase__    :	int     					=			1


      def 	_UpperCAmelCase (     self							) ->      Any:
             return self.data


      def 	_UpperCAmelCase (     self							) ->      MyNode | None:
             return self.left


      def 	_UpperCAmelCase (     self							) ->      MyNode | None:
             return self.right


      def 	_UpperCAmelCase (     self							) ->      int:
             return self.height


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             lowercase__    :	Optional[int]     					=			data


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             lowercase__    :	List[str]     					=			node


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             lowercase__    :	Tuple     					=			node


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             lowercase__    :	List[str]     					=			height





def        a_  (   _lowerCAmelCase						:				MyNode | None  ):





       '''simple docstring'''

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





def        a_  (   _lowerCAmelCase						:				int     ,				_lowerCAmelCase						:				int  ):





       '''simple docstring'''

       if a > b:
              return a
       return b





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       print('left rotation node:'     ,				node.get_data()  )
       lowercase__    :	List[str]     					=			node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()  )
       ret.set_right(_lowerCAmelCase  )
       lowercase__    :	Union[str, Any]     					=			my_max(get_height(node.get_right()  )     ,				get_height(node.get_left()  )  ) + 1
       node.set_height(_lowerCAmelCase  )
       lowercase__    :	Any     					=			my_max(get_height(ret.get_right()  )     ,				get_height(ret.get_left()  )  ) + 1
       ret.set_height(_lowerCAmelCase  )
       return ret





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       print('right rotation node:'     ,				node.get_data()  )
       lowercase__    :	List[str]     					=			node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()  )
       ret.set_left(_lowerCAmelCase  )
       lowercase__    :	Optional[Any]     					=			my_max(get_height(node.get_right()  )     ,				get_height(node.get_left()  )  ) + 1
       node.set_height(_lowerCAmelCase  )
       lowercase__    :	Optional[int]     					=			my_max(get_height(ret.get_right()  )     ,				get_height(ret.get_left()  )  ) + 1
       ret.set_height(_lowerCAmelCase  )
       return ret





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       lowercase__    :	Dict     					=			node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(_lowerCAmelCase  )  )
       return right_rotation(_lowerCAmelCase  )





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       lowercase__    :	List[str]     					=			node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(_lowerCAmelCase  )  )
       return left_rotation(_lowerCAmelCase  )





def        a_  (   _lowerCAmelCase						:				MyNode | None     ,				_lowerCAmelCase						:				Any  ):





       '''simple docstring'''

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





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       while True:
              lowercase__    :	Optional[int]     					=			root.get_right()
              if right_child is None:
                     break
              lowercase__    :	Any     					=			right_child
       return root.get_data()





def        a_  (   _lowerCAmelCase						:				MyNode  ):





       '''simple docstring'''

       while True:
              lowercase__    :	Optional[Any]     					=			root.get_left()
              if left_child is None:
                     break
              lowercase__    :	Tuple     					=			left_child
       return root.get_data()





def        a_  (   _lowerCAmelCase						:				MyNode     ,				_lowerCAmelCase						:				Any  ):





       '''simple docstring'''

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

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


class   UpperCAmelCase_			:


      def __init__(     self							) ->      None:
             lowercase__    :	MyNode | None     					=			None


      def 	_UpperCAmelCase (     self							) ->      int:
             return get_height(self.root							)


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             print('insert:' + str(__a							)							)
             lowercase__    :	Any     					=			insert_node(self.root	,    __a							)


      def 	_UpperCAmelCase (     self	,    a							) ->      None:
             print('delete:' + str(__a							)							)
             if self.root is None:
                    print('Tree is empty!'							)
                    return
             lowercase__    :	Union[str, Any]     					=			del_node(self.root	,    __a							)


      def __str__(     self	,    ) ->      str:  # a level traversale, gives a more intuitive look on the tree
             lowercase__    :	List[str]     					=			''
             lowercase__    :	Optional[int]     					=			MyQueue()
             q.push(self.root							)
             lowercase__    :	Union[str, Any]     					=			self.get_height()
             if layer == 0:
                    return output
             lowercase__    :	Union[str, Any]     					=			0
             while not q.is_empty():
                    lowercase__    :	Dict     					=			q.pop()
                    lowercase__    :	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
                    lowercase__    :	Optional[Any]     					=			cnt + 1
                    for i in range(1_0_0							):
                           if cnt == math.pow(2	,    __a							) - 1:
                                  lowercase__    :	Dict     					=			layer - 1
                                  if layer == 0:
                                         output += "\n*************************************"
                                         return output
                                  output += "\n"
                                  break
             output += "\n*************************************"
             return output





def        a_  (   ):





       '''simple docstring'''

       import doctest

       doctest.testmod()


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


"""simple docstring"""





def        a_  (   _lowerCAmelCase						:				str  ):





       '''simple docstring'''

       lowercase__    :	Any     					=			[0] * len(_lowerCAmelCase  )

       for i in range(1     ,				len(_lowerCAmelCase  )  ):
              # use last results for better performance - dynamic programming
              lowercase__    :	List[str]     					=			prefix_result[i - 1]
              while j > 0 and input_string[i] != input_string[j]:
                     lowercase__    :	Dict     					=			prefix_result[j - 1]

              if input_string[i] == input_string[j]:
                     j += 1
              lowercase__    :	Union[str, Any]     					=			j

       return prefix_result





def        a_  (   _lowerCAmelCase						:				str  ):





       '''simple docstring'''

       return max(prefix_function(_lowerCAmelCase  )  )


if __name__ == "__main__":
       import doctest

       doctest.testmod()

