




from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

UpperCamelCase								=					TypeVar('T')
UpperCamelCase								=					TypeVar('U')





class 			__lowerCamelCase	(   Generic[T, U]   ):




    """simple docstring"""

    def __init__(	self					:					Optional[Any]       ,     SCREAMING_SNAKE_CASE__					:					T | None       ,     SCREAMING_SNAKE_CASE__					:					U | None       )				->	List[str]:
         lowerCAmelCase__          =			key
         lowerCAmelCase__          =			val
         lowerCAmelCase__          =			None
         lowerCAmelCase__          =			None


    def __repr__(	self					:					Optional[int]       )				->	str:
         return (
             f'Node: key: {self.key}, val: {self.val}, '
             f'has next: {bool(self.next       )}, has prev: {bool(self.prev       )}'
         )






class 			__lowerCamelCase	(   Generic[T, U]   ):




    """simple docstring"""

    def __init__(	self					:					Optional[Any]       )				->	None:
         lowerCAmelCase__          =			DoubleLinkedListNode(SCREAMING_SNAKE_CASE__       ,     SCREAMING_SNAKE_CASE__       )
         lowerCAmelCase__          =			DoubleLinkedListNode(SCREAMING_SNAKE_CASE__       ,     SCREAMING_SNAKE_CASE__       )
         lowerCAmelCase__     ,		lowerCAmelCase__          =			self.rear, self.head


    def __repr__(	self					:					int       )				->	str:
         lowerCAmelCase__          =			["DoubleLinkedList"]
         lowerCAmelCase__          =			self.head
         while node.next is not None:
              rep.append(str(SCREAMING_SNAKE_CASE__       )       )
              lowerCAmelCase__          =			node.next
         rep.append(str(self.rear       )       )
         return ",\n    ".join(SCREAMING_SNAKE_CASE__       )


    def        a				(	self					:					Union[str, Any]       ,     SCREAMING_SNAKE_CASE__					:					DoubleLinkedListNode[T, U]       )				->	None:
         lowerCAmelCase__          =			self.rear.prev

         # All nodes other than self.head are guaranteed to have non-None previous
         assert previous is not None

         lowerCAmelCase__          =			node
         lowerCAmelCase__          =			previous
         lowerCAmelCase__          =			node
         lowerCAmelCase__          =			self.rear


    def        a				(	self					:					List[Any]       ,     SCREAMING_SNAKE_CASE__					:					DoubleLinkedListNode[T, U]       )				->	DoubleLinkedListNode[T, U] | None:

         if node.prev is None or node.next is None:
              return None

         lowerCAmelCase__          =			node.next
         lowerCAmelCase__          =			node.prev
         lowerCAmelCase__          =			None
         lowerCAmelCase__          =			None
         return node






class 			__lowerCamelCase	(   Generic[T, U]   ):




    """simple docstring"""

    snake_case__ =				{}


    def __init__(	self					:					List[str]       ,     SCREAMING_SNAKE_CASE__					:					int       )				->	int:
         lowerCAmelCase__          =			DoubleLinkedList()
         lowerCAmelCase__          =			capacity
         lowerCAmelCase__          =			0
         lowerCAmelCase__          =			0
         lowerCAmelCase__          =			0
         lowerCAmelCase__          =			{}


    def __repr__(	self					:					Tuple       )				->	str:
         return (
             f'CacheInfo(hits={self.hits}, misses={self.miss}, '
             f'capacity={self.capacity}, current size={self.num_keys})'
         )


    def __contains__(	self					:					Union[str, Any]       ,     SCREAMING_SNAKE_CASE__					:					T       )				->	bool:
         return key in self.cache


    def        a				(	self					:					Optional[int]       ,     SCREAMING_SNAKE_CASE__					:					T       )				->	U | None:
         # Note: pythonic interface would throw KeyError rather than return None

         if key in self.cache:
              self.hits += 1
              lowerCAmelCase__          =			self.cache[key]
              lowerCAmelCase__          =			self.list.remove(self.cache[key]       )
              assert node == value_node

              # node is guaranteed not None because it is in self.cache
              assert node is not None
              self.list.add(SCREAMING_SNAKE_CASE__       )
              return node.val
         self.miss += 1
         return None


    def        a				(	self					:					Union[str, Any]       ,     SCREAMING_SNAKE_CASE__					:					T       ,     SCREAMING_SNAKE_CASE__					:					U       )				->	None:

         if key not in self.cache:
              if self.num_keys >= self.capacity:
                   # delete first node (oldest) when over capacity
                   lowerCAmelCase__          =			self.list.head.next

                   # guaranteed to have a non-None first node when num_keys > 0
                   # explain to type checker via assertions
                   assert first_node is not None
                   assert first_node.key is not None
                   assert (
                       self.list.remove(SCREAMING_SNAKE_CASE__       ) is not None
                   )  # node guaranteed to be in list assert node.key is not None

                   del self.cache[first_node.key]
                   self.num_keys -= 1
              lowerCAmelCase__          =			DoubleLinkedListNode(SCREAMING_SNAKE_CASE__       ,     SCREAMING_SNAKE_CASE__       )
              self.list.add(self.cache[key]       )
              self.num_keys += 1

         else:
              # bump node to the end of the list, update value
              lowerCAmelCase__          =			self.list.remove(self.cache[key]       )
              assert node is not None  # node guaranteed to be in list
              lowerCAmelCase__          =			value
              self.list.add(SCREAMING_SNAKE_CASE__       )


    @classmethod
    def        a				(	cls					:					Optional[int]       ,     SCREAMING_SNAKE_CASE__					:					int = 128       )				->	Callable[[Callable[[T], U]], Callable[..., U]]:

         def cache_decorator_inner(SCREAMING_SNAKE_CASE__					:					Callable[[T], U]       ) -> Callable[..., U]:
              def cache_decorator_wrapper(*SCREAMING_SNAKE_CASE__					:					T       ) -> U:
                   if func not in cls.decorator_function_to_instance_map:
                        lowerCAmelCase__          =			LRUCache(SCREAMING_SNAKE_CASE__       )

                   lowerCAmelCase__          =			cls.decorator_function_to_instance_map[func].get(args[0]       )
                   if result is None:
                        lowerCAmelCase__          =			func(*SCREAMING_SNAKE_CASE__       )
                        cls.decorator_function_to_instance_map[func].put(args[0]       ,     SCREAMING_SNAKE_CASE__       )
                   return result

              def cache_info() -> LRUCache[T, U]:
                   return cls.decorator_function_to_instance_map[func]

              setattr(SCREAMING_SNAKE_CASE__       ,     "cache_info"       ,     SCREAMING_SNAKE_CASE__       )  # noqa: B010

              return cache_decorator_wrapper

         return cache_decorator_inner


if __name__ == "__main__":
     import doctest

     doctest.testmod()






import string



def 							_A       (						lowerCAmelCase_					: str      ):
     """simple docstring"""

     for key in range(len(string.ascii_uppercase      )      ):
          lowerCAmelCase__          =			""
          for symbol in message:
               if symbol in string.ascii_uppercase:
                    lowerCAmelCase__          =			string.ascii_uppercase.find(lowerCAmelCase_      )
                    lowerCAmelCase__          =			num - key
                    if num < 0:
                         lowerCAmelCase__          =			num + len(string.ascii_uppercase      )
                    lowerCAmelCase__          =			translated + string.ascii_uppercase[num]
               else:
                    lowerCAmelCase__          =			translated + symbol
          print(F'Decryption using Key #{key}: {translated}'      )



def 							_A       (						):
     """simple docstring"""

     lowerCAmelCase__          =			input("Encrypted message: "      )
     lowerCAmelCase__          =			message.upper()
     decrypt(lowerCAmelCase_      )


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     main()
