




def  UpperCAmelCase_							(				__UpperCAmelCase						:     int      ,      __UpperCAmelCase						:     Union[str, Any]							) ->			List[Any]:
      SCREAMING_SNAKE_CASE_     						=      0
      SCREAMING_SNAKE_CASE_     						=      len(__UpperCAmelCase							) - 1

      while left <= right:
            # avoid divided by 0 during interpolation
            if sorted_collection[left] == sorted_collection[right]:
                  if sorted_collection[left] == item:
                        return left
                  else:
                        return None

            SCREAMING_SNAKE_CASE_     						=      left + ((item - sorted_collection[left]) * (right - left)) // (
                sorted_collection[right] - sorted_collection[left]
            )

            # out of range check
            if point < 0 or point >= len(__UpperCAmelCase							):
                  return None

            SCREAMING_SNAKE_CASE_     						=      sorted_collection[point]
            if current_item == item:
                  return point
            else:
                  if point < left:
                        SCREAMING_SNAKE_CASE_     						=      left
                        SCREAMING_SNAKE_CASE_     						=      point
                  elif point > right:
                        SCREAMING_SNAKE_CASE_     						=      right
                        SCREAMING_SNAKE_CASE_     						=      point
                  else:
                        if item < current_item:
                              SCREAMING_SNAKE_CASE_     						=      point - 1
                        else:
                              SCREAMING_SNAKE_CASE_     						=      point + 1
      return None

def  UpperCAmelCase_							(				__UpperCAmelCase						:     Optional[int]      ,      __UpperCAmelCase						:     Optional[int]      ,      __UpperCAmelCase						:     Tuple      ,      __UpperCAmelCase						:     Tuple							) ->			List[str]:

      # avoid divided by 0 during interpolation
      if sorted_collection[left] == sorted_collection[right]:
            if sorted_collection[left] == item:
                  return left
            else:
                  return None

      SCREAMING_SNAKE_CASE_     						=      left + ((item - sorted_collection[left]) * (right - left)) // (
          sorted_collection[right] - sorted_collection[left]
      )

      # out of range check
      if point < 0 or point >= len(__UpperCAmelCase							):
            return None

      if sorted_collection[point] == item:
            return point
      elif point < left:
            return interpolation_search_by_recursion(__UpperCAmelCase      ,      __UpperCAmelCase      ,      __UpperCAmelCase      ,      __UpperCAmelCase							)
      elif point > right:
            return interpolation_search_by_recursion(__UpperCAmelCase      ,      __UpperCAmelCase      ,      __UpperCAmelCase      ,      __UpperCAmelCase							)
      else:
            if sorted_collection[point] > item:
                  return interpolation_search_by_recursion(
                      __UpperCAmelCase      ,      __UpperCAmelCase      ,      __UpperCAmelCase      ,      point - 1							)
            else:
                  return interpolation_search_by_recursion(
                      __UpperCAmelCase      ,      __UpperCAmelCase      ,      point + 1      ,      __UpperCAmelCase							)

def  UpperCAmelCase_							(				__UpperCAmelCase						:     str							) ->			List[str]:
      if collection != sorted(__UpperCAmelCase							):
            raise ValueError('Collection must be ascending sorted'							)
      return True


if __name__ == "__main__":
   import sys
   lowerCamelCase__			:       Dict         =							0
   if debug == 1:
      lowerCamelCase__			:       str         =							[10, 30, 40, 45, 50, 66, 77, 93]
      try:
         __assert_sorted(collection)
      except ValueError:
         sys.exit('Sequence must be ascending sorted to apply interpolation search')
      lowerCamelCase__			:       Union[str, Any]         =							67

   lowerCamelCase__			:       Tuple         =							interpolation_search(collection, target)
   if result is not None:
      print(f'''{target} found at positions: {result}''')
   else:
      print('Not found')





def  UpperCAmelCase_							(				__UpperCAmelCase						:     str							) ->			str:
      SCREAMING_SNAKE_CASE_     						=      ''
      for ch in key:
            if ch == " " or ch not in key_no_dups and ch.isalpha():
                  key_no_dups += ch
      return key_no_dups

def  UpperCAmelCase_							(				__UpperCAmelCase						:     str							) ->			dict[str, str]:
      SCREAMING_SNAKE_CASE_     						=      [chr(i + 65							) for i in range(26							)]
      # Remove duplicate characters from key
      SCREAMING_SNAKE_CASE_     						=      remove_duplicates(key.upper()							)
      SCREAMING_SNAKE_CASE_     						=      len(__UpperCAmelCase							)
      # First fill cipher with key characters
      SCREAMING_SNAKE_CASE_     						=      {alphabet[i]: char for i, char in enumerate(__UpperCAmelCase							)}
      # Then map remaining characters in alphabet to
      # the alphabet from the beginning
      for i in range(len(__UpperCAmelCase							)      ,      26							):
            SCREAMING_SNAKE_CASE_     						=      alphabet[i - offset]
            # Ensure we are not mapping letters to letters previously mapped
            while char in key:
                  offset -= 1
                  SCREAMING_SNAKE_CASE_     						=      alphabet[i - offset]
            SCREAMING_SNAKE_CASE_     						=      char
      return cipher_alphabet

def  UpperCAmelCase_							(				__UpperCAmelCase						:     str      ,      __UpperCAmelCase						:     dict[str, str]							) ->			str:
      return "".join(cipher_map.get(__UpperCAmelCase      ,      __UpperCAmelCase							) for ch in message.upper()							)

def  UpperCAmelCase_							(				__UpperCAmelCase						:     str      ,      __UpperCAmelCase						:     dict[str, str]							) ->			str:
      SCREAMING_SNAKE_CASE_     						=      {v: k for k, v in cipher_map.items()}
      return "".join(rev_cipher_map.get(__UpperCAmelCase      ,      __UpperCAmelCase							) for ch in message.upper()							)

def  UpperCAmelCase_							(				) ->			None:
      SCREAMING_SNAKE_CASE_     						=      input('Enter message to encode or decode: '							).strip()
      SCREAMING_SNAKE_CASE_     						=      input('Enter keyword: '							).strip()
      SCREAMING_SNAKE_CASE_     						=      input('Encipher or decipher? E/D:'							).strip()[0].lower()
      try:
            SCREAMING_SNAKE_CASE_     						=      {'e': encipher, 'd': decipher}[option]
      except KeyError:
            raise KeyError('invalid input option'							)
      SCREAMING_SNAKE_CASE_     						=      create_cipher_map(__UpperCAmelCase							)
      print(func(__UpperCAmelCase      ,      __UpperCAmelCase							)							)


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()