



from __future__ import annotations

import math
import random
from typing import Any



class 	lowerCamelCase      :







					'''simple docstring'''







					def __init__(			self     ):
							UpperCAmelCase_						=				[]
							UpperCAmelCase_						=				0
							UpperCAmelCase_						=				0



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



					def    A__		(			self    ,	lowerCAmelCase     ):
							self.data.append(lowerCAmelCase     )
							UpperCAmelCase_						=				self.tail + 1



					def    A__		(			self     ):
							UpperCAmelCase_						=				self.data[self.head]
							UpperCAmelCase_						=				self.head + 1
							return ret



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



					def    A__		(			self     ):
							print(self.data     )
							print("**************"     )
							print(self.data[self.head : self.tail]     )





class 	lowerCamelCase      :







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				data
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				1



					def    A__		(			self     ):
							return self.data



					def    A__		(			self     ):
							return self.left



					def    A__		(			self     ):
							return self.right



					def    A__		(			self     ):
							return self.height



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				data



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				node



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				node



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				height







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							int:
		if node is None:
				return 0
		return node.get_height()







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							int:
		if a > b:
				return a
		return b







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							MyNode:
		print("left rotation node:"			,     node.get_data() )
		UpperCAmelCase_						=				node.get_left()
		assert ret is not None
		node.set_left(ret.get_right() )
		ret.set_right(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				my_max(get_height(node.get_right() )			,     get_height(node.get_left() ) ) + 1
		node.set_height(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				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:
		print("right rotation node:"			,     node.get_data() )
		UpperCAmelCase_						=				node.get_right()
		assert ret is not None
		node.set_right(ret.get_left() )
		ret.set_left(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				my_max(get_height(node.get_right() )			,     get_height(node.get_left() ) ) + 1
		node.set_height(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				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:
		UpperCAmelCase_						=				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:
		UpperCAmelCase_						=				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			,     __SCREAMING_SNAKE_CASE )		->							MyNode | None:
		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
						UpperCAmelCase_						=				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_						=				right_rotation(__SCREAMING_SNAKE_CASE )
						else:
								UpperCAmelCase_						=				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:
						UpperCAmelCase_						=				node.get_right()
						assert right_child is not None
						if data < right_child.get_data():
								UpperCAmelCase_						=				rl_rotation(__SCREAMING_SNAKE_CASE )
						else:
								UpperCAmelCase_						=				left_rotation(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				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 )		->							Any:
		while True:
				UpperCAmelCase_						=				root.get_right()
				if right_child is None:
						break
				UpperCAmelCase_						=				right_child
		return root.get_data()







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							Any:
		while True:
				UpperCAmelCase_						=				root.get_left()
				if left_child is None:
						break
				UpperCAmelCase_						=				left_child
		return root.get_data()







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							MyNode | None:
		UpperCAmelCase_						=				root.get_left()
		UpperCAmelCase_						=				root.get_right()
		if root.get_data() == data:
				if left_child is not None and right_child is not None:
						UpperCAmelCase_						=				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:
						UpperCAmelCase_						=				left_child
				elif right_child is not None:
						UpperCAmelCase_						=				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() ):
						UpperCAmelCase_						=				left_rotation(__SCREAMING_SNAKE_CASE )
				else:
						UpperCAmelCase_						=				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() ):
						UpperCAmelCase_						=				right_rotation(__SCREAMING_SNAKE_CASE )
				else:
						UpperCAmelCase_						=				lr_rotation(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				my_max(get_height(root.get_right() )			,     get_height(root.get_left() ) ) + 1
		root.set_height(__SCREAMING_SNAKE_CASE )
		return root



class 	lowerCamelCase      :







					'''simple docstring'''







					def __init__(			self     ):
							UpperCAmelCase_						=				None



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



					def    A__		(			self    ,	lowerCAmelCase     ):
							print("insert:" + str(lowerCAmelCase     )     )
							UpperCAmelCase_						=				insert_node(self.root    ,	lowerCAmelCase     )



					def    A__		(			self    ,	lowerCAmelCase     ):
							print("delete:" + str(lowerCAmelCase     )     )
							if self.root is None:
									print("Tree is empty!"     )
									return
							UpperCAmelCase_						=				del_node(self.root    ,	lowerCAmelCase     )



					def __str__(			self    ,	):  # a level traversale, gives a more intuitive look on the tree
							UpperCAmelCase_						=				""
							UpperCAmelCase_						=				MyQueue()
							q.push(self.root     )
							UpperCAmelCase_						=				self.get_height()
							if layer == 0:
									return output
							UpperCAmelCase_						=				0
							while not q.is_empty():
									UpperCAmelCase_						=				q.pop()
									UpperCAmelCase_						=				" " * int(math.pow(2    ,	layer - 1     )     )
									output += space
									if node is None:
											output += "*"
											q.push(lowerCAmelCase     )
											q.push(lowerCAmelCase     )
									else:
											output += str(node.get_data()     )
											q.push(node.get_left()     )
											q.push(node.get_right()     )
									output += space
									UpperCAmelCase_						=				cnt + 1
									for i in range(100     ):
											if cnt == math.pow(2    ,	lowerCAmelCase     ) - 1:
													UpperCAmelCase_						=				layer - 1
													if layer == 0:
															output += "\n*************************************"
															return output
													output += "\n"
													break
							output += "\n*************************************"
							return output







def snake_case__  (			)		->							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))






def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							int:
		UpperCAmelCase_						=				1
		for i in range(1			,     num + 1 ):
				fact *= i
		return fact







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							int:
		UpperCAmelCase_						=				0
		while number > 0:
				UpperCAmelCase_						=				number % 10
				sum_of_digits += last_digit
				UpperCAmelCase_						=				number // 10  # Removing the last_digit from the given number
		return sum_of_digits







def snake_case__  (			__SCREAMING_SNAKE_CASE = 100 )		->							int:
		UpperCAmelCase_						=				factorial(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				split_and_add(__SCREAMING_SNAKE_CASE )
		return result


if __name__ == "__main__":
			print(solution(int(input("Enter the Number: ").strip())))

