



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

