






from __future__ import annotations




def   lowercase__   (  __snake_case					:							str  , __snake_case					:							dict[str, str]						):


					'''simple docstring'''


					UpperCAmelCase_					:   List[str]   =		'', '', ''
					UpperCAmelCase_					:   List[Any]   =		[]

					for character in message_part:
										tmp.append(character_to_number[character]						)

					for each in tmp:
										one += each[0]
										two += each[1]
										three += each[2]

					return one + two + three




def   lowercase__   (  __snake_case					:							str  , __snake_case					:							dict[str, str]						):


					'''simple docstring'''


					UpperCAmelCase_					:   Union[str, Any]   =		'', ''
					UpperCAmelCase_					:   Optional[int]   =		[]

					for character in message_part:
										this_part += character_to_number[character]

					for digit in this_part:
										tmp += digit
										if len(__snake_case						) == len(__snake_case						):
															result.append(__snake_case						)
															UpperCAmelCase_					:   List[Any]   =		''

					return result[0], result[1], result[2]




def   lowercase__   (  __snake_case					:							str  , __snake_case					:							str						):


					'''simple docstring'''


					UpperCAmelCase_					:   Tuple   =		alphabet.replace(' '  , ''						).upper()
					UpperCAmelCase_					:   List[str]   =		message.replace(' '  , ''						).upper()

					# Check length and characters
					if len(__snake_case						) != 27:
										raise KeyError('Length of alphabet has to be 27.'						)
					for each in message:
										if each not in alphabet:
															raise ValueError('Each message character has to be included in alphabet!'						)

    # Generate dictionares
					UpperCAmelCase_					:   str   =		(
					    '111',
					    '112',
					    '113',
					    '121',
					    '122',
					    '123',
					    '131',
					    '132',
					    '133',
					    '211',
					    '212',
					    '213',
					    '221',
					    '222',
					    '223',
					    '231',
					    '232',
					    '233',
					    '311',
					    '312',
					    '313',
					    '321',
					    '322',
					    '323',
					    '331',
					    '332',
					    '333',
					)
					UpperCAmelCase_					:   List[str]   =		{}
					UpperCAmelCase_					:   List[Any]   =		{}
					for letter, number in zip(__snake_case  , __snake_case						):
										UpperCAmelCase_					:   List[str]   =		number
										UpperCAmelCase_					:   List[Any]   =		letter

					return message, alphabet, character_to_number, number_to_character




def   lowercase__   (  __snake_case					:							str  , __snake_case					:							str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."  , __snake_case					:							int = 5						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		__prepare(
					    __snake_case  , __snake_case						)
					UpperCAmelCase_					:   Union[str, Any]   =		'', ''

					for i in range(0  , len(__snake_case						) + 1  , __snake_case						):
										encrypted_numeric += __encrypt_part(
										    message[i : i + period]  , __snake_case						)

					for i in range(0  , len(__snake_case						)  , 3						):
										encrypted += number_to_character[encrypted_numeric[i : i + 3]]

					return encrypted




def   lowercase__   (  __snake_case					:							str  , __snake_case					:							str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."  , __snake_case					:							int = 5						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		__prepare(
					    __snake_case  , __snake_case						)
					UpperCAmelCase_					:   Any   =		[]
					UpperCAmelCase_					:   Optional[int]   =		''

					for i in range(0  , len(__snake_case						) + 1  , __snake_case						):
										UpperCAmelCase_					:   int   =		__decrypt_part(message[i : i + period]  , __snake_case						)

										for j in range(0  , len(__snake_case						)						):
															decrypted_numeric.append(a[j] + b[j] + c[j]						)

					for each in decrypted_numeric:
										decrypted += number_to_character[each]

					return decrypted


if __name__ == "__main__":
		__UpperCAmelCase										=		'DEFEND THE EAST WALL OF THE CASTLE.'
		__UpperCAmelCase										=		encrypt_message(msg, 'EPSDUCVWYM.ZLKXNBTFGORIJHAQ')
		__UpperCAmelCase										=		decrypt_message(encrypted, 'EPSDUCVWYM.ZLKXNBTFGORIJHAQ')
		print(F'Encrypted: {encrypted}\nDecrypted: {decrypted}')














from __future__ import annotations




def   lowercase__   (  __snake_case					:							Any  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		0
					UpperCAmelCase_					:   Optional[int]   =		len(__snake_case						) - 1
					while left <= right:
										UpperCAmelCase_					:   Optional[Any]   =		(left + right) // 2
										if left == right:
															if sorted_list[middle] < item:
																				UpperCAmelCase_					:   List[Any]   =		middle + 1
															break
										elif sorted_list[middle] < item:
															UpperCAmelCase_					:   Union[str, Any]   =		middle + 1
										else:
															UpperCAmelCase_					:   Tuple   =		middle - 1
					sorted_list.insert(__snake_case  , __snake_case						)
					return sorted_list




def   lowercase__   (  __snake_case					:							Union[str, Any]  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		[]
					while left and right:
										if left[0][0] < right[0][0]:
															result.append(left.pop(0						)						)
										else:
															result.append(right.pop(0						)						)
					return result + left + right




def   lowercase__   (  __snake_case					:							Dict						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		len(__snake_case						)
					if length <= 1:
										return list_ad
					UpperCAmelCase_					:   List[Any]   =		length // 2
					return merge(sortlist_ad(list_ad[:middle]						)  , sortlist_ad(list_ad[middle:]						)						)




def   lowercase__   (  __snake_case					:							list[int]						):


					'''simple docstring'''


					if len(__snake_case						) <= 1:
										return collection
					UpperCAmelCase_					:   Any   =		[]
					UpperCAmelCase_					:   Union[str, Any]   =		False
					for i in range(0  , len(__snake_case						)  , 2						):
										if i == len(__snake_case						) - 1:
															UpperCAmelCase_					:   Tuple   =		True
										else:
															if collection[i] < collection[i + 1]:
																				two_paired_list.append([collection[i], collection[i + 1]]						)
															else:
																				two_paired_list.append([collection[i + 1], collection[i]]						)
					UpperCAmelCase_					:   Union[str, Any]   =		sortlist_ad(__snake_case						)
					UpperCAmelCase_					:   Any   =		[i[0] for i in sorted_list_ad]
					result.append(sorted_list_ad[-1][1]						)
					if has_last_odd_item:
										UpperCAmelCase_					:   Union[str, Any]   =		collection[-1]
										UpperCAmelCase_					:   List[Any]   =		binary_search_insertion(__snake_case  , __snake_case						)
					UpperCAmelCase_					:   Tuple   =		False
					for i in range(len(__snake_case						) - 1						):
										if result[i] == collection[-1] and has_last_odd_item:
															UpperCAmelCase_					:   List[Any]   =		True
										UpperCAmelCase_					:   Optional[int]   =		sorted_list_ad[i][1]
										# If last_odd_item is inserted before the item's index,
										# you should forward index one more.
										if is_last_odd_item_inserted_before_this_index:
															UpperCAmelCase_					:   List[str]   =		result[: i + 2] + binary_search_insertion(result[i + 2 :]  , __snake_case						)
										else:
															UpperCAmelCase_					:   List[Any]   =		result[: i + 1] + binary_search_insertion(result[i + 1 :]  , __snake_case						)

					return result


if __name__ == "__main__":
		__UpperCAmelCase										=		input('Enter numbers separated by a comma:\n').strip()
		__UpperCAmelCase										=		[int(item) for item in user_input.split(',')]
		print(merge_insertion_sort(unsorted))






