


'''simple docstring'''







def       lowercase					(_A ,    _A       ):







       """simple docstring"""







       _lowerCAmelCase     :				str       =							[[] for _ in range(_A       )]
       _lowerCAmelCase     :				Dict       =							key - 1

       if key <= 0:
              raise ValueError('Height of grid can\'t be 0 or negative'       )
       if key == 1 or len(_A       ) <= key:
              return input_string

       for position, character in enumerate(_A       ):
              _lowerCAmelCase     :				Tuple       =							position % (lowest * 2)  # puts it in bounds
              _lowerCAmelCase     :				List[Any]       =							min(_A ,    lowest * 2 - num       )  # creates zigzag pattern
              temp_grid[num].append(_A       )
       _lowerCAmelCase     :				Dict       =							[''.join(_A       ) for row in temp_grid]
       _lowerCAmelCase     :				int       =							''.join(_A       )

       return output_string






def       lowercase					(_A ,    _A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Optional[int]       =							[]
       _lowerCAmelCase     :				Any       =							key - 1

       if key <= 0:
              raise ValueError('Height of grid can\'t be 0 or negative'       )
       if key == 1:
              return input_string

       _lowerCAmelCase     :				List[Any]       =							[[] for _ in range(_A       )]  # generates template
       for position in range(len(_A       )       ):
              _lowerCAmelCase     :				Any       =							position % (lowest * 2)  # puts it in bounds
              _lowerCAmelCase     :				str       =							min(_A ,    lowest * 2 - num       )  # creates zigzag pattern
              temp_grid[num].append('*'       )

       _lowerCAmelCase     :				int       =							0
       for row in temp_grid:  # fills in the characters
              _lowerCAmelCase     :				List[str]       =							input_string[counter : counter + len(_A       )]
              grid.append(list(_A       )       )
              counter += len(_A       )

       _lowerCAmelCase     :				List[str]       =							''  # reads as zigzag
       for position in range(len(_A       )       ):
              _lowerCAmelCase     :				Union[str, Any]       =							position % (lowest * 2)  # puts it in bounds
              _lowerCAmelCase     :				List[str]       =							min(_A ,    lowest * 2 - num       )  # creates zigzag pattern
              output_string += grid[num][0]
              grid[num].pop(0       )
       return output_string






def       lowercase					(_A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Optional[Any]       =							{}
       for key_guess in range(1 ,    len(_A       )       ):  # tries every key
              _lowerCAmelCase     :				Optional[int]       =							decrypt(_A ,    _A       )
       return results


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


