
from __future__ import annotations

import math
import random
from typing import Any





class       __A:

					def __init__(	self					:     Dict   ):
												lowerCamelCase_							  =					[]
												lowerCamelCase_							  =					0
												lowerCamelCase_							  =					0

					def    lowercase__      (	self					:     Optional[int]   ):
												return self.head == self.tail

					def    lowercase__      (	self					:     int   ,					__UpperCamelCase					:     Any   ):
												self.data.append(__UpperCamelCase   )
												lowerCamelCase_							  =					self.tail + 1

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

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



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





class       __A:

					def __init__(	self					:     Union[str, Any]   ,					__UpperCamelCase					:     Any   ):
												lowerCamelCase_							  =					data
												lowerCamelCase_							  =					None
												lowerCamelCase_							  =					None
												lowerCamelCase_							  =					1

					def    lowercase__      (	self					:     Union[str, Any]   ):
												return self.data

					def    lowercase__      (	self					:     Dict   ):
												return self.left

					def    lowercase__      (	self					:     Union[str, Any]   ):
												return self.right

					def    lowercase__      (	self					:     Any   ):
												return self.height

					def    lowercase__      (	self					:     Any   ,					__UpperCamelCase					:     Any   ):
												lowerCamelCase_							  =					data

					def    lowercase__      (	self					:     str   ,					__UpperCamelCase					:     MyNode | None   ):
												lowerCamelCase_							  =					node

					def    lowercase__      (	self					:     Tuple   ,					__UpperCamelCase					:     MyNode | None   ):
												lowerCamelCase_							  =					node



					def    lowercase__      (	self					:     int   ,					__UpperCamelCase					:     int   ):
												lowerCamelCase_							  =					height



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



def      __lowerCAmelCase						(							UpperCAmelCase__				:      int			,				UpperCAmelCase__				:      int       )  ->    int:
							if a > b:
														return a
							return b



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    MyNode:
							print("""left rotation node:"""			,				node.get_data()       )
							lowerCamelCase_							  =					node.get_left()
							assert ret is not None
							node.set_left(ret.get_right()       )
							ret.set_right(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(node.get_right()       )			,				get_height(node.get_left()       )       ) + 1
							node.set_height(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(ret.get_right()       )			,				get_height(ret.get_left()       )       ) + 1
							ret.set_height(UpperCAmelCase__       )
							return ret



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    MyNode:
							print("""right rotation node:"""			,				node.get_data()       )
							lowerCamelCase_							  =					node.get_right()
							assert ret is not None
							node.set_right(ret.get_left()       )
							ret.set_left(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(node.get_right()       )			,				get_height(node.get_left()       )       ) + 1
							node.set_height(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(ret.get_right()       )			,				get_height(ret.get_left()       )       ) + 1
							ret.set_height(UpperCAmelCase__       )
							return ret



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    MyNode:
							lowerCamelCase_							  =					node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(UpperCAmelCase__       )       )
							return right_rotation(UpperCAmelCase__       )



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    MyNode:
							lowerCamelCase_							  =					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:
							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
																					lowerCamelCase_							  =					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
																												lowerCamelCase_							  =					right_rotation(UpperCAmelCase__       )
																					else:
																												lowerCamelCase_							  =					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:
																					lowerCamelCase_							  =					node.get_right()
																					assert right_child is not None
																					if data < right_child.get_data():
																												lowerCamelCase_							  =					rl_rotation(UpperCAmelCase__       )
																					else:
																												lowerCamelCase_							  =					left_rotation(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(node.get_right()       )			,				get_height(node.get_left()       )       ) + 1
							node.set_height(UpperCAmelCase__       )
							return node



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    Any:
							while True:
														lowerCamelCase_							  =					root.get_right()
														if right_child is None:
																					break
														lowerCamelCase_							  =					right_child
							return root.get_data()



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode       )  ->    Any:
							while True:
														lowerCamelCase_							  =					root.get_left()
														if left_child is None:
																					break
														lowerCamelCase_							  =					left_child
							return root.get_data()



def      __lowerCAmelCase						(							UpperCAmelCase__				:      MyNode			,				UpperCAmelCase__				:      Any       )  ->    MyNode | None:
							lowerCamelCase_							  =					root.get_left()
							lowerCamelCase_							  =					root.get_right()
							if root.get_data() == data:
														if left_child is not None and right_child is not None:
																					lowerCamelCase_							  =					get_left_most(UpperCAmelCase__       )
																					root.set_data(UpperCAmelCase__       )
																					root.set_right(del_node(UpperCAmelCase__			,				UpperCAmelCase__       )       )
														elif left_child is not None:
																					lowerCamelCase_							  =					left_child
														elif right_child is not None:
																					lowerCamelCase_							  =					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()       ):
																					lowerCamelCase_							  =					left_rotation(UpperCAmelCase__       )
														else:
																					lowerCamelCase_							  =					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()       ):
																					lowerCamelCase_							  =					right_rotation(UpperCAmelCase__       )
														else:
																					lowerCamelCase_							  =					lr_rotation(UpperCAmelCase__       )
							lowerCamelCase_							  =					my_max(get_height(root.get_right()       )			,				get_height(root.get_left()       )       ) + 1
							root.set_height(UpperCAmelCase__       )
							return root





class       __A:

					def __init__(	self					:     List[Any]   ):
												lowerCamelCase_							  =					None

					def    lowercase__      (	self					:     str   ):
												return get_height(self.root   )

					def    lowercase__      (	self					:     int   ,					__UpperCamelCase					:     Any   ):
												print("""insert:""" + str(__UpperCamelCase   )   )
												lowerCamelCase_							  =					insert_node(self.root   ,					__UpperCamelCase   )

					def    lowercase__      (	self					:     Union[str, Any]   ,					__UpperCamelCase					:     Any   ):
												print("""delete:""" + str(__UpperCamelCase   )   )
												if self.root is None:
																			print("""Tree is empty!"""   )
																			return
												lowerCamelCase_							  =					del_node(self.root   ,					__UpperCamelCase   )



					def __str__(	self					:     Tuple   ,					):  # a level traversale, gives a more intuitive look on the tree
												lowerCamelCase_							  =					""""""
												lowerCamelCase_							  =					MyQueue()
												q.push(self.root   )
												lowerCamelCase_							  =					self.get_height()
												if layer == 0:
																			return output
												lowerCamelCase_							  =					0
												while not q.is_empty():
																			lowerCamelCase_							  =					q.pop()
																			lowerCamelCase_							  =					""" """ * 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
																			lowerCamelCase_							  =					cnt + 1
																			for i in range(1_0_0   ):
																										if cnt == math.pow(2   ,					__UpperCamelCase   ) - 1:
																																	lowerCamelCase_							  =					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()
		lowercase        =  AVLtree()
		lowercase        =  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))







def      __lowerCAmelCase						(							UpperCAmelCase__				:      int = 4_0_0_0_0_0_0       )  ->    int:
							lowerCamelCase_							  =					[]
							lowerCamelCase_  ,   lowerCamelCase_							  =					0, 1
							while b <= n:
														if b % 2 == 0:
																					even_fibs.append(UpperCAmelCase__       )
														lowerCamelCase_  ,   lowerCamelCase_							  =					b, a + b
							return sum(UpperCAmelCase__       )


if __name__ == "__main__":
		print(F"""{solution() = }""")





