

from __future__ import annotations

import math
import random
from typing import Any


class 				SCREAMING_SNAKE_CASE__ :





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





				def 				snake_case_    (				self):
									return self.head == self.tail





				def 				snake_case_    (				self						,       a):
									self.data.append(a)
									lowercase__   :       int				=	self.tail + 1





				def 				snake_case_    (				self):
									lowercase__   :       str				=	self.data[self.head]
									lowercase__   :       Tuple				=	self.head + 1
									return ret





				def 				snake_case_    (				self):
									return self.tail - self.head





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



class 				SCREAMING_SNAKE_CASE__ :





				def __init__(				self						,       a):
									lowercase__   :       Union[str, Any]				=	data
									lowercase__   :       MyNode | None				=	None
									lowercase__   :       MyNode | None				=	None
									lowercase__   :       int				=	1





				def 				snake_case_    (				self):
									return self.data





				def 				snake_case_    (				self):
									return self.left





				def 				snake_case_    (				self):
									return self.right





				def 				snake_case_    (				self):
									return self.height





				def 				snake_case_    (				self						,       a):
									lowercase__   :       Dict				=	data





				def 				snake_case_    (				self						,       a):
									lowercase__   :       Tuple				=	node





				def 				snake_case_    (				self						,       a):
									lowercase__   :       List[str]				=	node





				def 				snake_case_    (				self						,       a):
									lowercase__   :       Optional[int]				=	height



def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode | None      ):



					'''simple docstring'''





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

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int     ,					SCREAMING_SNAKE_CASE_		:   int      ):



					'''simple docstring'''





					if a > b:
										return a
					return b

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   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(SCREAMING_SNAKE_CASE_      )
					lowercase__   :       str				=	my_max(get_height(node.get_right()      )     ,					get_height(node.get_left()      )      ) + 1
					node.set_height(SCREAMING_SNAKE_CASE_      )
					lowercase__   :       List[str]				=	my_max(get_height(ret.get_right()      )     ,					get_height(ret.get_left()      )      ) + 1
					ret.set_height(SCREAMING_SNAKE_CASE_      )
					return ret

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode      ):



					'''simple docstring'''





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

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode      ):



					'''simple docstring'''





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

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode      ):



					'''simple docstring'''





					lowercase__   :       Any				=	node.get_right()
					assert right_child is not None
					node.set_right(right_rotation(SCREAMING_SNAKE_CASE_      )      )
					return left_rotation(SCREAMING_SNAKE_CASE_      )

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode | None     ,					SCREAMING_SNAKE_CASE_		:   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
															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__   :       str				=	right_rotation(SCREAMING_SNAKE_CASE_      )
															else:
																				lowercase__   :       Any				=	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:
															lowercase__   :       str				=	node.get_right()
															assert right_child is not None
															if data < right_child.get_data():
																				lowercase__   :       List[str]				=	rl_rotation(SCREAMING_SNAKE_CASE_      )
															else:
																				lowercase__   :       Optional[int]				=	left_rotation(SCREAMING_SNAKE_CASE_      )
					lowercase__   :       Dict				=	my_max(get_height(node.get_right()      )     ,					get_height(node.get_left()      )      ) + 1
					node.set_height(SCREAMING_SNAKE_CASE_      )
					return node

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode      ):



					'''simple docstring'''





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

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   MyNode      ):



					'''simple docstring'''





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

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



					'''simple docstring'''





					lowercase__   :       Union[str, Any]				=	root.get_left()
					lowercase__   :       Any				=	root.get_right()
					if root.get_data() == data:
										if left_child is not None and right_child is not None:
															lowercase__   :       str				=	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:
															lowercase__   :       List[Any]				=	left_child
										elif right_child is not None:
															lowercase__   :       int				=	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()      ):
															lowercase__   :       Any				=	left_rotation(SCREAMING_SNAKE_CASE_      )
										else:
															lowercase__   :       Union[str, Any]				=	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()      ):
															lowercase__   :       Any				=	right_rotation(SCREAMING_SNAKE_CASE_      )
										else:
															lowercase__   :       int				=	lr_rotation(SCREAMING_SNAKE_CASE_      )
					lowercase__   :       List[Any]				=	my_max(get_height(root.get_right()      )     ,					get_height(root.get_left()      )      ) + 1
					root.set_height(SCREAMING_SNAKE_CASE_      )
					return root


class 				SCREAMING_SNAKE_CASE__ :





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





				def 				snake_case_    (				self):
									return get_height(self.root)





				def 				snake_case_    (				self						,       a):
									print('insert:' + str(a))
									lowercase__   :       str				=	insert_node(self.root						,       a)





				def 				snake_case_    (				self						,       a):
									print('delete:' + str(a))
									if self.root is None:
														print('Tree is empty!')
														return
									lowercase__   :       Optional[Any]				=	del_node(self.root						,       a)





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



def      snake_case__      (   ):



					'''simple docstring'''





					import doctest

					doctest.testmod()


if __name__ == "__main__":
							_test()
							snake_case_        =			AVLtree()
							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 __future__ import annotations

from collections.abc import Callable

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   Callable[[int | float], int | float]     ,					SCREAMING_SNAKE_CASE_		:   int | float     ,					SCREAMING_SNAKE_CASE_		:   int | float     ,					SCREAMING_SNAKE_CASE_		:   int = 100     ,					):



     '''simple docstring'''





     lowercase__   :       Tuple				=	x_start
     lowercase__   :       Tuple				=	fnc(SCREAMING_SNAKE_CASE_      )
     lowercase__   :       List[Any]				=	0.0
     for _ in range(SCREAMING_SNAKE_CASE_      ):
          # Approximates small segments of curve as linear and solve
          # for trapezoidal area
          lowercase__   :       Any				=	(x_end - x_start) / steps + xa
          lowercase__   :       Optional[Any]				=	fnc(SCREAMING_SNAKE_CASE_      )
          area += abs(fxa + fxa      ) * (xa - xa) / 2
          # Increment step
          lowercase__   :       Any				=	xa
          lowercase__   :       str				=	fxa
     return area


if __name__ == "__main__":

       def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   Tuple      ):



            '''simple docstring'''





            return x**3 + x**2

       print('''f(x) = x^3 + x^2''')
       print('''The area between the curve, x = -5, x = 5 and the x axis is:''')
       snake_case_        =			10
       while i <= 100_000:
              print(F'''with {i} steps: {trapezoidal_area(f, -5, 5, i)}''')
              i *= 10

