


from __future__ import annotations

def 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					Any       ,						__UpperCamelCase				:					Optional[int]		)				->  tuple[float, float]:







     """simple docstring"""
     assert (
         c % greatest_common_divisor(lowerCamelCase__       ,						lowerCamelCase__		) == 0
     )  # greatest_common_divisor(a,b) function implemented below
     ((_A)		,							(_A)		,							(_A))				=       extended_gcd(lowerCamelCase__       ,						lowerCamelCase__		)  # extended_gcd(a,b) function implemented below
     _A				=       c / d
     return (r * x, r * y)

def 				lowerCamelCase_   (   __UpperCamelCase				:					List[Any]       ,						__UpperCamelCase				:					Optional[Any]       ,						__UpperCamelCase				:					List[str]       ,						__UpperCamelCase				:					Any = 2		)				->  None:







     """simple docstring"""
     ((_A)		,							(_A))				=       diophantine(lowerCamelCase__       ,						lowerCamelCase__       ,						lowerCamelCase__		)  # Initial value
     _A				=       greatest_common_divisor(lowerCamelCase__       ,						lowerCamelCase__		)
     _A				=       a // d
     _A				=       b // d

     for i in range(lowerCamelCase__		):
          _A				=       xa + i * q
          _A				=       ya - i * p
          print(lowerCamelCase__       ,						lowerCamelCase__		)

def 				lowerCamelCase_   (   __UpperCamelCase				:					Optional[int]       ,						__UpperCamelCase				:					Optional[Any]		)				->  int:







     """simple docstring"""




     if a < b:
          _A		,							_A				=       b, a

     while a % b != 0:
          _A		,							_A				=       b, a % b

     return b

def 				lowerCamelCase_   (   __UpperCamelCase				:					Union[str, Any]       ,						__UpperCamelCase				:					List[Any]		)				->  tuple[int, int, int]:







     """simple docstring"""
     assert a >= 0 and b >= 0

     if b == 0:
          _A		,							_A		,							_A				=       a, 1, 0
     else:
          ((_A)		,							(_A)		,							(_A))				=       extended_gcd(lowerCamelCase__       ,						a % b		)
          _A				=       q
          _A				=       p - q * (a // b)

     assert a % d == 0 and b % d == 0
     assert d == a * x + b * y

     return (d, x, y)


if __name__ == "__main__":
    from doctest import testmod

    testmod(name="""diophantine""", verbose=True)
    testmod(name="""diophantine_all_soln""", verbose=True)
    testmod(name="""extended_gcd""", verbose=True)
    testmod(name="""greatest_common_divisor""", verbose=True)









'''simple docstring'''
from __future__ import annotations

def 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					dict[str, str]		)				->  str:







     """simple docstring"""
     _A		,							_A		,							_A				=       '', '', ''
     _A				=       []

     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 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					dict[str, str]		)				->  tuple[str, str, str]:







     """simple docstring"""
     _A		,							_A				=       '', ''
     _A				=       []

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

     for digit in this_part:
          tmp += digit
          if len(__UpperCamelCase		) == len(__UpperCamelCase		):
               result.append(__UpperCamelCase		)
               _A				=       ''

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

def 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					str		)				->  tuple[str, str, dict[str, str], dict[str, str]]:







     """simple docstring"""
     # Validate message and alphabet, set to upper and remove spaces
     _A				=       alphabet.replace(' '       ,						''		).upper()
     _A				=       message.replace(' '       ,						''		).upper()

     # Check length and characters
     if len(__UpperCamelCase		) != 2_7:
          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
     _A				=       (
         '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',
     )
     _A				=       {}
     _A				=       {}
     for letter, number in zip(__UpperCamelCase       ,						__UpperCamelCase		):
          _A				=       number
          _A				=       letter

     return message, alphabet, character_to_number, number_to_character

def 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."       ,						__UpperCamelCase				:					int = 5		)				->  str:







     """simple docstring"""
     _A		,							_A		,							_A		,							_A				=       __prepare(
         __UpperCamelCase       ,						__UpperCamelCase		)
     _A		,							_A				=       '', ''

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

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

     return encrypted

def 				lowerCamelCase_   (   __UpperCamelCase				:					str       ,						__UpperCamelCase				:					str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."       ,						__UpperCamelCase				:					int = 5		)				->  str:







     """simple docstring"""
     _A		,							_A		,							_A		,							_A				=       __prepare(
         __UpperCamelCase       ,						__UpperCamelCase		)
     _A				=       []
     _A				=       ''

     for i in range(0       ,						len(__UpperCamelCase		) + 1       ,						__UpperCamelCase		):
          _A		,							_A		,							_A				=       __decrypt_part(message[i : i + period]       ,						__UpperCamelCase		)

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

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

     return decrypted


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





