
from __future__ import annotations

import math
import random
from typing import Any






class        __lowercase		:


					def __init__(						self    )		->				None:





									'''simple docstring'''
									A_													=	[]
									A_													=	0
									A_													=	0


					def 							lowerCAmelCase_     (						self    )		->				bool:





									'''simple docstring'''
									return self.head == self.tail


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									self.data.append(a__    )
									A_													=	self.tail + 1


					def 							lowerCAmelCase_     (						self    )		->				Any:





									'''simple docstring'''
									A_													=	self.data[self.head]
									A_													=	self.head + 1
									return ret


					def 							lowerCAmelCase_     (						self    )		->				int:





									'''simple docstring'''
									return self.tail - self.head


					def 							lowerCAmelCase_     (						self    )		->				None:





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






class        __lowercase		:


					def __init__(						self							,							a__    )		->				None:





									'''simple docstring'''
									A_													=	data
									A_													=	None
									A_													=	None
									A_													=	1


					def 							lowerCAmelCase_     (						self    )		->				Any:





									'''simple docstring'''
									return self.data


					def 							lowerCAmelCase_     (						self    )		->				MyNode | None:





									'''simple docstring'''
									return self.left


					def 							lowerCAmelCase_     (						self    )		->				MyNode | None:





									'''simple docstring'''
									return self.right


					def 							lowerCAmelCase_     (						self    )		->				int:





									'''simple docstring'''
									return self.height


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									A_													=	data


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									A_													=	node


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									A_													=	node


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									A_													=	height



def 							lowerCamelCase_	( __UpperCamelCase  ):






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



def 							lowerCamelCase_	( __UpperCamelCase			,    __UpperCamelCase  ):






				if a > b:
								return a
				return b



def 							lowerCamelCase_	( __UpperCamelCase  ):
				print('''left rotation node:'''			,    node.get_data()  )
				A_													=	node.get_left()
				assert ret is not None
				node.set_left(ret.get_right()  )
				ret.set_right(a__  )
				A_													=	my_max(get_height(node.get_right()  )			,    get_height(node.get_left()  )  ) + 1
				node.set_height(a__  )
				A_													=	my_max(get_height(ret.get_right()  )			,    get_height(ret.get_left()  )  ) + 1
				ret.set_height(a__  )
				return ret



def 							lowerCamelCase_	( __UpperCamelCase  ):
				print('''right rotation node:'''			,    node.get_data()  )
				A_													=	node.get_right()
				assert ret is not None
				node.set_right(ret.get_left()  )
				ret.set_left(a__  )
				A_													=	my_max(get_height(node.get_right()  )			,    get_height(node.get_left()  )  ) + 1
				node.set_height(a__  )
				A_													=	my_max(get_height(ret.get_right()  )			,    get_height(ret.get_left()  )  ) + 1
				ret.set_height(a__  )
				return ret



def 							lowerCamelCase_	( __UpperCamelCase  ):
				A_													=	node.get_left()
				assert left_child is not None
				node.set_left(left_rotation(a__  )  )
				return right_rotation(a__  )



def 							lowerCamelCase_	( __UpperCamelCase  ):
				A_													=	node.get_right()
				assert right_child is not None
				node.set_right(right_rotation(a__  )  )
				return left_rotation(a__  )



def 							lowerCamelCase_	( __UpperCamelCase			,    __UpperCamelCase  ):






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



def 							lowerCamelCase_	( __UpperCamelCase  ):






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



def 							lowerCamelCase_	( __UpperCamelCase  ):






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



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






class        __lowercase		:


					def __init__(						self    )		->				None:





									'''simple docstring'''
									A_													=	None


					def 							lowerCAmelCase_     (						self    )		->				int:





									'''simple docstring'''
									return get_height(self.root    )


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									print('''insert:''' + str(a__    )    )
									A_													=	insert_node(self.root							,							a__    )


					def 							lowerCAmelCase_     (						self							,							a__    )		->				None:





									'''simple docstring'''
									print('''delete:''' + str(a__    )    )
									if self.root is None:
													print('''Tree is empty!'''    )
													return
									A_													=	del_node(self.root							,							a__    )


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





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



def 							lowerCamelCase_	( ):
				import doctest

				doctest.testmod()


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


from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass




@dataclass
class 						__UpperCamelCase     :
					lowercase_    :				int
					lowercase_    :				TreeNode | None      =  None
					lowercase_    :				TreeNode | None      =  None


__SCREAMING_SNAKE_CASE   =   namedtuple('CoinsDistribResult', 'moves excess')


def        UpperCAmelCase      (					a__ ):





						'''simple docstring'''






						if root is None:
												return 0

						# Validation
						def count_nodes(a__ ) -> int:
												if node is None:
																		return 0

												return count_nodes(node.left ) + count_nodes(node.right ) + 1

						def count_coins(a__ ) -> int:
												if node is None:
																		return 0

												return count_coins(node.left ) + count_coins(node.right ) + node.data

						if count_nodes(a__ ) != count_coins(a__ ):
												raise ValueError('The nodes number should be same as the number of coins' )

						# Main calculation
						def get_distrib(a__ ) -> CoinsDistribResult:

												if node is None:
																		return CoinsDistribResult(0     ,      1 )

												lowerCAmelCase	, lowerCAmelCase   :Optional[int]						=			get_distrib(node.left )
												lowerCAmelCase	, lowerCAmelCase   :str						=			get_distrib(node.right )

												lowerCAmelCase   :str						=			1 - left_distrib_excess
												lowerCAmelCase   :Optional[Any]						=			1 - right_distrib_excess

												lowerCAmelCase   :Any						=			(
												    left_distrib_moves
												    + right_distrib_moves
												    + abs(a__ )
												    + abs(a__ )
												)
												lowerCAmelCase   :Tuple						=			node.data - coins_to_left - coins_to_right

												return CoinsDistribResult(a__     ,      a__ )

						return get_distrib(a__ )[0]


if __name__ == "__main__":
		import doctest

		doctest.testmod()