

'''simple docstring'''
from collections.abc import Generator
from math import sin


def  a__       (    _SCREAMING_SNAKE_CASE   :       bytes				)     ->					bytes:


	"""simple docstring"""





	if len(_SCREAMING_SNAKE_CASE				) != 32:
		raise ValueError("Input must be of length 32"				)

	UpperCAmelCase_     :      Optional[Any]						=  B""
	for i in [3, 2, 1, 0]:
		little_endian += string_aa[8 * i : 8 * i + 8]
	return little_endian


def  a__       (    _SCREAMING_SNAKE_CASE   :       int				)     ->					bytes:


	"""simple docstring"""





	if i < 0:
		raise ValueError("Input must be non-negative"				)

	UpperCAmelCase_     :      Tuple						=  format(_SCREAMING_SNAKE_CASE	,				"08x"				)[-8:]
	UpperCAmelCase_     :      Tuple						=  B""
	for i in [3, 2, 1, 0]:
		little_endian_hex += hex_rep[2 * i : 2 * i + 2].encode("utf-8"				)
	return little_endian_hex


def  a__       (    _SCREAMING_SNAKE_CASE   :       bytes				)     ->					bytes:


	"""simple docstring"""





	UpperCAmelCase_     :      List[Any]						=  B""
	for char in message:
		bit_string += format(_SCREAMING_SNAKE_CASE	,				"08b"				).encode("utf-8"				)
	UpperCAmelCase_     :      Optional[Any]						=  format(len(_SCREAMING_SNAKE_CASE				)	,				"064b"				).encode("utf-8"				)

	# Pad bit_string to a multiple of 512 chars
	bit_string += b"1"
	while len(_SCREAMING_SNAKE_CASE				) % 5_12 != 4_48:
		bit_string += b"0"
	bit_string += to_little_endian(start_len[32:]				) + to_little_endian(start_len[:32]				)

	return bit_string


def  a__       (    _SCREAMING_SNAKE_CASE   :       bytes				)     ->					Generator[list[int], None, None]:


	"""simple docstring"""





	if len(_SCREAMING_SNAKE_CASE				) % 5_12 != 0:
		raise ValueError("Input must have length that's a multiple of 512"				)

	for pos in range(0	,				len(_SCREAMING_SNAKE_CASE				)	,				5_12				):
		UpperCAmelCase_     :      List[str]						=  bit_string[pos : pos + 5_12]
		UpperCAmelCase_     :      List[Any]						=  []
		for i in range(0	,				5_12	,				32				):
			block_words.append(int(to_little_endian(block[i : i + 32]				)	,				2				)				)
		yield block_words


def  a__       (    _SCREAMING_SNAKE_CASE   :       int				)     ->					int:


	"""simple docstring"""





	if i < 0:
		raise ValueError("Input must be non-negative"				)

	UpperCAmelCase_     :      List[Any]						=  format(_SCREAMING_SNAKE_CASE	,				"032b"				)
	UpperCAmelCase_     :      Tuple						=  ""
	for c in i_str:
		new_str += "1" if c == "0" else "0"
	return int(_SCREAMING_SNAKE_CASE	,				2				)


def  a__       (    _SCREAMING_SNAKE_CASE   :       int	,				_SCREAMING_SNAKE_CASE   :       int				)     ->					int:


	"""simple docstring"""





	return (a + b) % 2**32


def  a__       (    _SCREAMING_SNAKE_CASE   :       int	,				_SCREAMING_SNAKE_CASE   :       int				)     ->					int:


	"""simple docstring"""





	if i < 0:
		raise ValueError("Input must be non-negative"				)
	if shift < 0:
		raise ValueError("Shift must be non-negative"				)
	return ((i << shift) ^ (i >> (32 - shift))) % 2**32


def  a__       (    _SCREAMING_SNAKE_CASE   :       bytes				)     ->					bytes:


	"""simple docstring"""





	UpperCAmelCase_     :      str						=  preprocess(_SCREAMING_SNAKE_CASE				)

	UpperCAmelCase_     :      List[Any]						=  [int(2**32 * abs(sin(i + 1				)				)				) for i in range(64				)]

	# Starting states
	UpperCAmelCase_     :      Any						=  0x6_7_4_5_2_3_0_1
	UpperCAmelCase_     :      Optional[int]						=  0xe_f_c_d_a_b_8_9
	UpperCAmelCase_     :      Dict						=  0x9_8_b_a_d_c_f_e
	UpperCAmelCase_     :      List[str]						=  0x1_0_3_2_5_4_7_6

	UpperCAmelCase_     :      Tuple						=  [
	    7,
	    12,
	    17,
	    22,
	    7,
	    12,
	    17,
	    22,
	    7,
	    12,
	    17,
	    22,
	    7,
	    12,
	    17,
	    22,
	    5,
	    9,
	    14,
	    20,
	    5,
	    9,
	    14,
	    20,
	    5,
	    9,
	    14,
	    20,
	    5,
	    9,
	    14,
	    20,
	    4,
	    11,
	    16,
	    23,
	    4,
	    11,
	    16,
	    23,
	    4,
	    11,
	    16,
	    23,
	    4,
	    11,
	    16,
	    23,
	    6,
	    10,
	    15,
	    21,
	    6,
	    10,
	    15,
	    21,
	    6,
	    10,
	    15,
	    21,
	    6,
	    10,
	    15,
	    21,
	]

	# Process bit string in chunks, each with 16 32-char words
	for block_words in get_block_words(_SCREAMING_SNAKE_CASE				):
		UpperCAmelCase_     :      Union[str, Any]						=  aa
		UpperCAmelCase_     :      Optional[Any]						=  ba
		UpperCAmelCase_     :      int						=  ca
		UpperCAmelCase_     :      Dict						=  da

		# Hash current chunk
		for i in range(64				):
			if i <= 15:
				# f = (b & c) | (not_32(b) & d)     # Alternate definition for f
				UpperCAmelCase_     :      List[Any]						=  d ^ (b & (c ^ d))
				UpperCAmelCase_     :      int						=  i
			elif i <= 31:
				# f = (d & b) | (not_32(d) & c)     # Alternate definition for f
				UpperCAmelCase_     :      List[Any]						=  c ^ (d & (b ^ c))
				UpperCAmelCase_     :      Tuple						=  (5 * i + 1) % 16
			elif i <= 47:
				UpperCAmelCase_     :      List[Any]						=  b ^ c ^ d
				UpperCAmelCase_     :      List[str]						=  (3 * i + 5) % 16
			else:
				UpperCAmelCase_     :      str						=  c ^ (b | not_aa(_SCREAMING_SNAKE_CASE				))
				UpperCAmelCase_     :      Dict						=  (7 * i) % 16
			UpperCAmelCase_     :      Dict						=  (f + a + added_consts[i] + block_words[g]) % 2**32
			UpperCAmelCase_     :      Dict						=  d
			UpperCAmelCase_     :      str						=  c
			UpperCAmelCase_     :      str						=  b
			UpperCAmelCase_     :      str						=  sum_aa(_SCREAMING_SNAKE_CASE	,				left_rotate_aa(_SCREAMING_SNAKE_CASE	,				shift_amounts[i]				)				)

		# Add hashed chunk to running total
		UpperCAmelCase_     :      Dict						=  sum_aa(_SCREAMING_SNAKE_CASE	,				_SCREAMING_SNAKE_CASE				)
		UpperCAmelCase_     :      int						=  sum_aa(_SCREAMING_SNAKE_CASE	,				_SCREAMING_SNAKE_CASE				)
		UpperCAmelCase_     :      str						=  sum_aa(_SCREAMING_SNAKE_CASE	,				_SCREAMING_SNAKE_CASE				)
		UpperCAmelCase_     :      Tuple						=  sum_aa(_SCREAMING_SNAKE_CASE	,				_SCREAMING_SNAKE_CASE				)

	UpperCAmelCase_     :      int						=  reformat_hex(_SCREAMING_SNAKE_CASE				) + reformat_hex(_SCREAMING_SNAKE_CASE				) + reformat_hex(_SCREAMING_SNAKE_CASE				) + reformat_hex(_SCREAMING_SNAKE_CASE				)
	return digest


if __name__ == "__main__":
					import doctest

					doctest.testmod()








from __future__ import annotations

import math
import random
from typing import Any







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							[]
						UpperCamelCase__       =							0
						UpperCamelCase__       =							0




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.head == self.tail




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						self.data.append(snake_case  )
						UpperCamelCase__       =							self.tail + 1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							self.data[self.head]
						UpperCamelCase__       =							self.head + 1
						return ret




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.tail - self.head







			def 					snake_case__					(				self  ):

						'''simple docstring'''


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







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data
						UpperCamelCase__       =							None
						UpperCamelCase__       =							None
						UpperCamelCase__       =							1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.data




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.left




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.right




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.height




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node







			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							height



def 							UpperCamelCase_(					_A :MyNode | None	)->		int:
			if node is None:
						return 0
			return node.get_height()
def 							UpperCamelCase_(					_A :int					,  _A :int	)->		int:
			if a > b:
						return a
			return b
def 							UpperCamelCase_(					_A :MyNode	)->		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(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		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(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_left()
			assert left_child is not None
			node.set_left(left_rotation(_A	)	)
			return right_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_right()
			assert right_child is not None
			node.set_right(right_rotation(_A	)	)
			return left_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode | None					,  _A :Any	)->		MyNode | None:
			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
									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(_A	)
									else:
												UpperCamelCase__       =							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:
									UpperCamelCase__       =							node.get_right()
									assert right_child is not None
									if data < right_child.get_data():
												UpperCamelCase__       =							rl_rotation(_A	)
									else:
												UpperCamelCase__       =							left_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			return node
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_right()
						if right_child is None:
									break
						UpperCamelCase__       =							right_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_left()
						if left_child is None:
									break
						UpperCamelCase__       =							left_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode					,  _A :Any	)->		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(_A	)
									root.set_data(_A	)
									root.set_right(del_node(_A					,  _A	)	)
						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(_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()	):
									UpperCamelCase__       =							left_rotation(_A	)
						else:
									UpperCamelCase__       =							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()	):
									UpperCamelCase__       =							right_rotation(_A	)
						else:
									UpperCamelCase__       =							lr_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(root.get_right()	)					,  get_height(root.get_left()	)	) + 1
			root.set_height(_A	)
			return root







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							None




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return get_height(self.root  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("insert:" + str(snake_case  )  )
						UpperCamelCase__       =							insert_node(self.root   ,    snake_case  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("delete:" + str(snake_case  )  )
						if self.root is None:
									print("Tree is empty!"  )
									return
						UpperCamelCase__       =							del_node(self.root   ,    snake_case  )







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

						'''simple docstring'''


						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(snake_case  )
												q.push(snake_case  )
									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   ,    snake_case  ) - 1:
															UpperCamelCase__       =							layer - 1
															if layer == 0:
																		output += "\n*************************************"
																		return output
															output += "\n"
															break
						output += "\n*************************************"
						return output



def 							UpperCamelCase_(					)->		None:
			import doctest

			doctest.testmod()


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


