






import string

import numpy






def    __magic_name__    (	SCREAMING_SNAKE_CASE     ,     SCREAMING_SNAKE_CASE				)     ->    int:
							return b if a == 0 else greatest_common_divisor(b % a     ,     SCREAMING_SNAKE_CASE				)

class 				lowerCAmelCase_	:
				_UpperCamelCase					:       Any							       = string.ascii_uppercase + string.digits
				# This cipher takes alphanumerics into account
				# i.e. a total of 36 characters

				# take x and return x % len(key_string)
				_UpperCamelCase					:       Tuple							       = numpy.vectorize(lambda __snake_case			: x % 36			)

				_UpperCamelCase					:       Any							       = numpy.vectorize(__snake_case			)


				def __init__(					self ,						_lowerCAmelCase      ):
											_lowercase							:   str 							=   self.modulus(_lowerCAmelCase      )  # mod36 calc's on the encrypt key
											self.check_determinant()  # validate the determinant of the encryption key
											_lowercase							:   int 							=   encrypt_key.shape[0]


				def 						__a					(					self ,						_lowerCAmelCase      ):
											return self.key_string.index(_lowerCAmelCase      )


				def 						__a					(					self ,						_lowerCAmelCase      ):
											return self.key_string[round(_lowerCAmelCase      )]


				def 						__a					(					self      ):
											_lowercase							:   str 							=   round(numpy.linalg.det(self.encrypt_key      )      )

											if det < 0:
																		_lowercase							:   int 							=   det % len(self.key_string      )

											_lowercase							:   List[str] 							=   len(self.key_string      )
											if greatest_common_divisor(_lowerCAmelCase ,						len(self.key_string      )      ) != 1:
																		_lowercase							:   str 							=   (
																		    F"""determinant modular {req_l} of encryption key({det}) """
																		    F"""is not co prime w.r.t {req_l}.\nTry another key."""
																		)
																		raise ValueError(_lowerCAmelCase      )


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							:   Optional[Any] 							=   [char for char in text.upper() if char in self.key_string]

											_lowercase							:   Union[str, Any] 							=   chars[-1]
											while len(_lowerCAmelCase      ) % self.break_key != 0:
																		chars.append(_lowerCAmelCase      )

											return "".join(_lowerCAmelCase      )


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							:   Optional[int] 							=   self.process_text(text.upper()      )
											_lowercase							:   Dict 							=   ''

											for i in range(0 ,						len(_lowerCAmelCase      ) - self.break_key + 1 ,						self.break_key      ):
																		_lowercase							:   List[Any] 							=   text[i : i + self.break_key]
																		_lowercase							:   str 							=   [self.replace_letters(_lowerCAmelCase      ) for char in batch]
																		_lowercase							:   Union[str, Any] 							=   numpy.array([vec]      ).T
																		_lowercase							:   List[Any] 							=   self.modulus(self.encrypt_key.dot(_lowerCAmelCase      )      ).T.tolist()[
																		    0
																		]
																		_lowercase							:   Any 							=   ''.join(
																		    self.replace_digits(_lowerCAmelCase      ) for num in batch_encrypted      )
																		encrypted += encrypted_batch

											return encrypted


				def 						__a					(					self      ):
											_lowercase							:   Any 							=   round(numpy.linalg.det(self.encrypt_key      )      )

											if det < 0:
																		_lowercase							:   Any 							=   det % len(self.key_string      )
											_lowercase							:   Any 							=   None
											for i in range(len(self.key_string      )      ):
																		if (det * i) % len(self.key_string      ) == 1:
																									_lowercase							:   Union[str, Any] 							=   i
																									break

											_lowercase							:   List[str] 							=   (
											    det_inv
											    * numpy.linalg.det(self.encrypt_key      )
											    * numpy.linalg.inv(self.encrypt_key      )
											)

											return self.to_int(self.modulus(_lowerCAmelCase      )      )


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							:   Optional[int] 							=   self.make_decrypt_key()
											_lowercase							:   Union[str, Any] 							=   self.process_text(text.upper()      )
											_lowercase							:   List[str] 							=   ''

											for i in range(0 ,						len(_lowerCAmelCase      ) - self.break_key + 1 ,						self.break_key      ):
																		_lowercase							:   List[Any] 							=   text[i : i + self.break_key]
																		_lowercase							:   Any 							=   [self.replace_letters(_lowerCAmelCase      ) for char in batch]
																		_lowercase							:   Optional[int] 							=   numpy.array([vec]      ).T
																		_lowercase							:   int 							=   self.modulus(decrypt_key.dot(_lowerCAmelCase      )      ).T.tolist()[0]
																		_lowercase							:   str 							=   ''.join(
																		    self.replace_digits(_lowerCAmelCase      ) for num in batch_decrypted      )
																		decrypted += decrypted_batch

											return decrypted






def    __magic_name__    (	)     ->    None:
							_lowercase							:   Any 							=   int(input('Enter the order of the encryption key: '				)				)
							_lowercase							:   Any 							=   []

							print('Enter each row of the encryption key with space separated integers'				)
							for _ in range(SCREAMING_SNAKE_CASE				):
														_lowercase							:   Tuple 							=   [int(SCREAMING_SNAKE_CASE				) for x in input().split()]
														hill_matrix.append(SCREAMING_SNAKE_CASE				)

							_lowercase							:   int 							=   HillCipher(numpy.array(SCREAMING_SNAKE_CASE				)				)

							print('Would you like to encrypt or decrypt some text? (1 or 2)'				)
							_lowercase							:   List[str] 							=   input('\n1. Encrypt\n2. Decrypt\n'				)
							if option == "1":
														_lowercase							:   int 							=   input('What text would you like to encrypt?: '				)
														print('Your encrypted text is:'				)
														print(hc.encrypt(SCREAMING_SNAKE_CASE				)				)
							elif option == "2":
														_lowercase							:   List[str] 							=   input('What text would you like to decrypt?: '				)
														print('Your decrypted text is:'				)
														print(hc.decrypt(SCREAMING_SNAKE_CASE				)				)


if __name__ == "__main__":
							import doctest

							doctest.testmod()

							main()






'''simple docstring'''
lowerCAmelCase					:    Optional[Any]           = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['A', 'B', 'D'],
    'F': ['C'],
    'G': ['C'],
}







def 		A_(     A						:		dict		,     A						:		str		,     A						:		Optional[Any]):
							UpperCamelCase   			=     set()
							# keep track of all the paths to be checked
							UpperCamelCase   			=     [[start]]

							# return path if start is goal
							if start == goal:
														return [start]

							# keeps looping until all possible paths have been checked
							while queue:
														# pop the first path from the queue
														UpperCamelCase   			=     queue.pop(0)
														# get the last node from the path
														UpperCamelCase   			=     path[-1]
														if node not in explored:
																					UpperCamelCase   			=     graph[node]
																					# go through all neighbour nodes, construct a new path and
																					# push it into the queue
																					for neighbour in neighbours:
																												UpperCamelCase   			=     list(A)
																												new_path.append(A)
																												queue.append(A)
																												# return path if neighbour is goal
																												if neighbour == goal:
																																			return new_path

            # mark node as explored
																					explored.add(A)

    # in case there's no path between the 2 nodes
							return []







def 		A_(     A						:		dict		,     A						:		str		,     A						:		Tuple):
							if not graph or start not in graph or target not in graph:
														return -1
							if start == target:
														return 0
							UpperCamelCase   			=     [start]
							UpperCamelCase   			=     set(A)
							# Keep tab on distances from `start` node.
							UpperCamelCase   			=     {start: 0, target: -1}
							while queue:
														UpperCamelCase   			=     queue.pop(0)
														if node == target:
																					UpperCamelCase   			=     (
																					    dist[node] if dist[target] == -1 else min(dist[target]		,     dist[node])
																					)
														for adjacent in graph[node]:
																					if adjacent not in visited:
																												visited.add(A)
																												queue.append(A)
																												UpperCamelCase   			=     dist[node] + 1
							return dist[target]


if __name__ == "__main__":
						print(bfs_shortest_path(demo_graph, 'G', 'D'))  # returns ['G', 'C', 'A', 'B', 'D']
						print(bfs_shortest_path_distance(demo_graph, 'G', 'D'))  # returns 4




