"""simple docstring"""


from __future__ import annotations

import unittest
from collections.abc import Iterator





class 					snake_case			:

				def __init__(			self							:       Optional[Any]  ,						UpperCamelCase__							:       Any  ,						UpperCamelCase__							:       List[Any])->     str:



						'''simple docstring'''


						__lowerCAmelCase: int					   =    label
						__lowerCAmelCase: Optional[Any]					   =    parent
						__lowerCAmelCase: int					   =    None
						__lowerCAmelCase: str					   =    None





class 					snake_case			:

				def __init__(			self							:       int)->     str:



						'''simple docstring'''


						__lowerCAmelCase: Union[str, Any]					   =    None

				def 							lowercase_  (			self							:       List[str])->     Tuple:



						'''simple docstring'''


						__lowerCAmelCase: str					   =    None

				def 							lowercase_  (			self							:       Tuple)->     Dict:



						'''simple docstring'''


						return self.root is None

				def 							lowercase_  (			self							:       Dict  ,						UpperCamelCase__							:       List[str])->     Optional[Any]:



						'''simple docstring'''


						__lowerCAmelCase: Union[str, Any]					   =    self._put(self.root  ,						__snake_case)

				def 							lowercase_  (			self							:       List[Any]  ,						UpperCamelCase__							:       Any  ,						UpperCamelCase__							:       List[Any]  ,						UpperCamelCase__							:       Optional[Any] = None)->     Union[str, Any]:



						'''simple docstring'''


						if node is None:
								__lowerCAmelCase: Optional[Any]					   =    Node(__snake_case  ,						__snake_case)
						else:
								if label < node.label:
										__lowerCAmelCase: List[str]					   =    self._put(node.left  ,						__snake_case  ,						__snake_case)
								elif label > node.label:
										__lowerCAmelCase: Optional[Any]					   =    self._put(node.right  ,						__snake_case  ,						__snake_case)
								else:
										__lowerCAmelCase: Dict					   =    f"Node with label {label} already exists"
										raise Exception(__snake_case)

						return node

				def 							lowercase_  (			self							:       Dict  ,						UpperCamelCase__							:       List[Any])->     Union[str, Any]:



						'''simple docstring'''


						return self._search(self.root  ,						__snake_case)

				def 							lowercase_  (			self							:       Optional[Any]  ,						UpperCamelCase__							:       Optional[Any]  ,						UpperCamelCase__							:       List[Any])->     List[Any]:



						'''simple docstring'''


						if node is None:
								__lowerCAmelCase: Union[str, Any]					   =    f"Node with label {label} does not exist"
								raise Exception(__snake_case)
						else:
								if label < node.label:
										__lowerCAmelCase: int					   =    self._search(node.left  ,						__snake_case)
								elif label > node.label:
										__lowerCAmelCase: Optional[int]					   =    self._search(node.right  ,						__snake_case)

						return node

				def 							lowercase_  (			self							:       Any  ,						UpperCamelCase__							:       Union[str, Any])->     List[str]:



						'''simple docstring'''


						__lowerCAmelCase: List[Any]					   =    self.search(__snake_case)
						if node.right and node.left:
								__lowerCAmelCase: Optional[Any]					   =    self._get_lowest_node(node.right)
								__lowerCAmelCase: int					   =    node.left
								__lowerCAmelCase: Optional[int]					   =    node.right
								__lowerCAmelCase: Tuple					   =    lowest_node
								if node.right:
										__lowerCAmelCase: Optional[int]					   =    lowest_node
								self._reassign_nodes(__snake_case  ,						__snake_case)
						elif not node.right and node.left:
								self._reassign_nodes(__snake_case  ,						node.left)
						elif node.right and not node.left:
								self._reassign_nodes(__snake_case  ,						node.right)
						else:
								self._reassign_nodes(__snake_case  ,						__snake_case)

				def 							lowercase_  (			self							:       Tuple  ,						UpperCamelCase__							:       Optional[int]  ,						UpperCamelCase__							:       List[Any])->     Tuple:



						'''simple docstring'''


						if new_children:
								__lowerCAmelCase: str					   =    node.parent

						if node.parent:
								if node.parent.right == node:
										__lowerCAmelCase: Tuple					   =    new_children
								else:
										__lowerCAmelCase: str					   =    new_children
						else:
								__lowerCAmelCase: Optional[Any]					   =    new_children

				def 							lowercase_  (			self							:       List[str]  ,						UpperCamelCase__							:       Optional[int])->     Optional[int]:



						'''simple docstring'''


						if node.left:
								__lowerCAmelCase: Tuple					   =    self._get_lowest_node(node.left)
						else:
								__lowerCAmelCase: Dict					   =    node
								self._reassign_nodes(__snake_case  ,						node.right)

						return lowest_node

				def 							lowercase_  (			self							:       str  ,						UpperCamelCase__							:       Optional[Any])->     str:



						'''simple docstring'''


						try:
								self.search(__snake_case)
								return True
						except Exception:
								return False

				def 							lowercase_  (			self							:       Optional[Any])->     Any:



						'''simple docstring'''


						if self.root is None:
								raise Exception("Binary search tree is empty")

						__lowerCAmelCase: Tuple					   =    self.root
						while node.right is not None:
								__lowerCAmelCase: Any					   =    node.right

						return node.label

				def 							lowercase_  (			self							:       Union[str, Any])->     List[str]:



						'''simple docstring'''


						if self.root is None:
								raise Exception("Binary search tree is empty")

						__lowerCAmelCase: Optional[int]					   =    self.root
						while node.left is not None:
								__lowerCAmelCase: List[str]					   =    node.left

						return node.label

				def 							lowercase_  (			self							:       str)->     Optional[int]:



						'''simple docstring'''


						return self._inorder_traversal(self.root)

				def 							lowercase_  (			self							:       str  ,						UpperCamelCase__							:       List[Any])->     int:



						'''simple docstring'''


						if node is not None:
								yield from self._inorder_traversal(node.left)
								yield node
								yield from self._inorder_traversal(node.right)

				def 							lowercase_  (			self							:       Tuple)->     Dict:



						'''simple docstring'''


						return self._preorder_traversal(self.root)




				def 							lowercase_  (			self							:       str  ,						UpperCamelCase__							:       Union[str, Any])->     List[str]:



						'''simple docstring'''


						if node is not None:
								yield node
								yield from self._preorder_traversal(node.left)
								yield from self._preorder_traversal(node.right)





class 					snake_case			(       unittest.TestCase						):

				@staticmethod
				def 							lowercase_  (			)->     int:



						'''simple docstring'''


						__lowerCAmelCase: Union[str, Any]					   =    BinarySearchTree()
						t.put(8)
						t.put(3)
						t.put(6)
						t.put(1)
						t.put(1_0)
						t.put(1_4)
						t.put(1_3)
						t.put(4)
						t.put(7)
						t.put(5)

						return t

				def 							lowercase_  (			self							:       Dict)->     Tuple:



						'''simple docstring'''


						__lowerCAmelCase: List[str]					   =    BinarySearchTree()
						assert t.is_empty()

						t.put(8)
						assert t.root is not None
						assert t.root.parent is None
						assert t.root.label == 8

						t.put(1_0)
						assert t.root.right is not None
						assert t.root.right.parent == t.root
						assert t.root.right.label == 1_0

						t.put(3)
						assert t.root.left is not None
						assert t.root.left.parent == t.root
						assert t.root.left.label == 3

						t.put(6)
						assert t.root.left.right is not None
						assert t.root.left.right.parent == t.root.left
						assert t.root.left.right.label == 6

						t.put(1)
						assert t.root.left.left is not None
						assert t.root.left.left.parent == t.root.left
						assert t.root.left.left.label == 1

						with self.assertRaises(__snake_case):  # noqa: B017
								t.put(1)

				def 							lowercase_  (			self							:       Optional[Any])->     Any:



						'''simple docstring'''


						__lowerCAmelCase: Any					   =    self._get_binary_search_tree()

						__lowerCAmelCase: int					   =    t.search(6)
						assert node.label == 6

						__lowerCAmelCase: Tuple					   =    t.search(1_3)
						assert node.label == 1_3

						with self.assertRaises(__snake_case):  # noqa: B017
								t.search(2)

				def 							lowercase_  (			self							:       List[Any])->     int:



						'''simple docstring'''


						__lowerCAmelCase: Any					   =    self._get_binary_search_tree()

						t.remove(1_3)
						assert t.root is not None
						assert t.root.right is not None
						assert t.root.right.right is not None
						assert t.root.right.right.right is None
						assert t.root.right.right.left is None

						t.remove(7)
						assert t.root.left is not None
						assert t.root.left.right is not None
						assert t.root.left.right.left is not None
						assert t.root.left.right.right is None
						assert t.root.left.right.left.label == 4

						t.remove(6)
						assert t.root.left.left is not None
						assert t.root.left.right.right is not None
						assert t.root.left.left.label == 1
						assert t.root.left.right.label == 4
						assert t.root.left.right.right.label == 5
						assert t.root.left.right.left is None
						assert t.root.left.left.parent == t.root.left
						assert t.root.left.right.parent == t.root.left

						t.remove(3)
						assert t.root is not None
						assert t.root.left.label == 4
						assert t.root.left.right.label == 5
						assert t.root.left.left.label == 1
						assert t.root.left.parent == t.root
						assert t.root.left.left.parent == t.root.left
						assert t.root.left.right.parent == t.root.left

						t.remove(4)
						assert t.root.left is not None
						assert t.root.left.left is not None
						assert t.root.left.label == 5
						assert t.root.left.right is None
						assert t.root.left.left.label == 1
						assert t.root.left.parent == t.root
						assert t.root.left.left.parent == t.root.left

				def 							lowercase_  (			self							:       Union[str, Any])->     str:



						'''simple docstring'''


						__lowerCAmelCase: Dict					   =    self._get_binary_search_tree()

						t.remove(3)
						assert t.root is not None
						assert t.root.left is not None
						assert t.root.left.left is not None
						assert t.root.left.right is not None
						assert t.root.left.right.left is not None
						assert t.root.left.right.right is not None
						assert t.root.left.label == 4
						assert t.root.left.right.label == 6
						assert t.root.left.left.label == 1
						assert t.root.left.right.right.label == 7
						assert t.root.left.right.left.label == 5
						assert t.root.left.parent == t.root
						assert t.root.left.right.parent == t.root.left
						assert t.root.left.left.parent == t.root.left
						assert t.root.left.right.left.parent == t.root.left.right

				def 							lowercase_  (			self							:       List[str])->     Dict:



						'''simple docstring'''


						__lowerCAmelCase: Optional[Any]					   =    self._get_binary_search_tree()
						t.empty()
						assert t.root is None

				def 							lowercase_  (			self							:       Optional[int])->     Optional[int]:



						'''simple docstring'''


						__lowerCAmelCase: Optional[Any]					   =    self._get_binary_search_tree()
						assert not t.is_empty()

						t.empty()
						assert t.is_empty()

				def 							lowercase_  (			self							:       Tuple)->     Tuple:



						'''simple docstring'''


						__lowerCAmelCase: str					   =    self._get_binary_search_tree()

						assert t.exists(6)
						assert not t.exists(-1)

				def 							lowercase_  (			self							:       Union[str, Any])->     List[Any]:



						'''simple docstring'''


						__lowerCAmelCase: Tuple					   =    self._get_binary_search_tree()

						assert t.get_max_label() == 1_4

						t.empty()
						with self.assertRaises(__snake_case):  # noqa: B017
								t.get_max_label()

				def 							lowercase_  (			self							:       List[str])->     Tuple:



						'''simple docstring'''


						__lowerCAmelCase: Tuple					   =    self._get_binary_search_tree()

						assert t.get_min_label() == 1

						t.empty()
						with self.assertRaises(__snake_case):  # noqa: B017
								t.get_min_label()

				def 							lowercase_  (			self							:       Union[str, Any])->     Tuple:



						'''simple docstring'''


						__lowerCAmelCase: Tuple					   =    self._get_binary_search_tree()

						__lowerCAmelCase: Union[str, Any]					   =    [i.label for i in t.inorder_traversal()]
						assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]




				def 							lowercase_  (			self							:       str)->     List[Any]:



						'''simple docstring'''


						__lowerCAmelCase: Dict					   =    self._get_binary_search_tree()

						__lowerCAmelCase: Union[str, Any]					   =    [i.label for i in t.preorder_traversal()]
						assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]






def 					a__					(					)			->			List[Any]:
		__lowerCAmelCase: Dict					   =    BinarySearchTree()
		t.put(8				)
		t.put(3				)
		t.put(6				)
		t.put(1				)
		t.put(1_0				)
		t.put(1_4				)
		t.put(1_3				)
		t.put(4				)
		t.put(7				)
		t.put(5				)

		print(
		    "\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        "				)

		print("Label 6 exists:"      ,				t.exists(6				)				)
		print("Label 13 exists:"      ,				t.exists(1_3				)				)
		print("Label -1 exists:"      ,				t.exists(-1				)				)
		print("Label 12 exists:"      ,				t.exists(1_2				)				)

		# Prints all the elements of the list in inorder traversal
		__lowerCAmelCase: int					   =    [i.label for i in t.inorder_traversal()]
		print("Inorder traversal:"      ,				UpperCamelCase_				)

		# Prints all the elements of the list in preorder traversal
		__lowerCAmelCase: Tuple					   =    [i.label for i in t.preorder_traversal()]
		print("Preorder traversal:"      ,				UpperCamelCase_				)

		print("Max. label:"      ,				t.get_max_label()				)
		print("Min. label:"      ,				t.get_min_label()				)

		# Delete elements
		print("\nDeleting elements 13, 10, 8, 3, 6, 14"				)
		print(
		    "\n          4\n         / \\\n        1   7\n             \\\n              5\n        "				)
		t.remove(1_3				)
		t.remove(1_0				)
		t.remove(8				)
		t.remove(3				)
		t.remove(6				)
		t.remove(1_4				)

		# Prints all the elements of the list in inorder traversal after delete
		__lowerCAmelCase: Union[str, Any]					   =    [i.label for i in t.inorder_traversal()]
		print("Inorder traversal after delete:"      ,				UpperCamelCase_				)

		# Prints all the elements of the list in preorder traversal after delete
		__lowerCAmelCase: Optional[Any]					   =    [i.label for i in t.preorder_traversal()]
		print("Preorder traversal after delete:"      ,				UpperCamelCase_				)

		print("Max. label:"      ,				t.get_max_label()				)
		print("Min. label:"      ,				t.get_min_label()				)


if __name__ == "__main__":
			binary_search_tree_example()





"""simple docstring"""


import random
import sys

__A		     =    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"






def 					a__					(					)			->			None:
		__lowerCAmelCase: int					   =    input("Enter message: "				)
		__lowerCAmelCase: Any					   =    "LFWOAYUISVKMNXPBDCRJTQEGHZ"
		__lowerCAmelCase: int					   =    input("Encrypt/Decrypt [e/d]: "				)

		check_valid_key(__SCREAMING_SNAKE_CASE				)

		if resp.lower().startswith("e"				):
				__lowerCAmelCase: Tuple					   =    "encrypt"
				__lowerCAmelCase: int					   =    encrypt_message(__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)
		elif resp.lower().startswith("d"				):
				__lowerCAmelCase: str					   =    "decrypt"
				__lowerCAmelCase: List[str]					   =    decrypt_message(__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)

		print(F"\n{mode.title()}ion: \n{translated}"				)






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			None:
		__lowerCAmelCase: List[Any]					   =    list(__SCREAMING_SNAKE_CASE				)
		__lowerCAmelCase: Optional[int]					   =    list(__SCREAMING_SNAKE_CASE				)
		key_list.sort()
		letters_list.sort()

		if key_list != letters_list:
				sys.exit("Error in the key or symbol set."				)






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			str:
		return translate_message(__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE      ,				"encrypt"				)






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			str:
		return translate_message(__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE      ,				"decrypt"				)






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			str:
		__lowerCAmelCase: Union[str, Any]					   =    ""
		__lowerCAmelCase: List[str]					   =    LETTERS
		__lowerCAmelCase: Optional[int]					   =    key

		if mode == "decrypt":
				__lowerCAmelCase   ,				__lowerCAmelCase: Optional[int]					   =    chars_b, chars_a

		for symbol in message:
				if symbol.upper() in chars_a:
						__lowerCAmelCase: Union[str, Any]					   =    chars_a.find(symbol.upper()				)
						if symbol.isupper():
								translated += chars_b[sym_index].upper()
						else:
								translated += chars_b[sym_index].lower()
				else:
						translated += symbol

		return translated






def 					a__					(					)			->			str:
		__lowerCAmelCase: int					   =    list(__SCREAMING_SNAKE_CASE				)
		random.shuffle(__SCREAMING_SNAKE_CASE				)
		return "".join(__SCREAMING_SNAKE_CASE				)


if __name__ == "__main__":
			main()


