






from __future__ import annotations

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

SCREAMING_SNAKE_CASE__   :      str				=		TypeVar("""T""")
SCREAMING_SNAKE_CASE__   :      int				=		TypeVar("""U""")
class     lowerCamelCase_					(   Generic[T, U]			):







				def __init__(    self							,       __lowerCAmelCase							,       __lowerCAmelCase  ):
								"""simple docstring"""
								__magic_name__		:Tuple   =   key
								__magic_name__		:List[str]   =   val
								__magic_name__		:DoubleLinkedListNode[T, U] | None   =   None
								__magic_name__		:DoubleLinkedListNode[T, U] | None   =   None







				def __repr__(    self  ):
								"""simple docstring"""
								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]			):







				def __init__(    self  ):
								"""simple docstring"""
								__magic_name__		:DoubleLinkedListNode[T, U]   =   DoubleLinkedListNode(__lowerCAmelCase							,       __lowerCAmelCase  )
								__magic_name__		:DoubleLinkedListNode[T, U]   =   DoubleLinkedListNode(__lowerCAmelCase							,       __lowerCAmelCase  )
								__magic_name__  ,					__magic_name__		:Union[str, Any]   =   self.rear, self.head







				def __repr__(    self  ):
								"""simple docstring"""
								__magic_name__		:Any   =   ['''DoubleLinkedList''']
								__magic_name__		:Any   =   self.head
								while node.next is not None:
												rep.append(str(__lowerCAmelCase  )  )
												__magic_name__		:Optional[int]   =   node.next
								rep.append(str(self.rear  )  )
								return ",\n    ".join(__lowerCAmelCase  )







				def       A						(    self							,       __lowerCAmelCase  ):
								"""simple docstring"""
								__magic_name__		:List[Any]   =   self.rear.prev

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

								__magic_name__		:str   =   node
								__magic_name__		:str   =   previous
								__magic_name__		:Dict   =   node
								__magic_name__		:Optional[Any]   =   self.rear







				def       A						(    self							,       __lowerCAmelCase  ):
								"""simple docstring"""

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

								__magic_name__		:str   =   node.next
								__magic_name__		:Any   =   node.prev
								__magic_name__		:int   =   None
								__magic_name__		:List[str]   =   None
								return node







class     lowerCamelCase_					(   Generic[T, U]			):
				a__       							=	{}







				def __init__(    self							,       __lowerCAmelCase  ):
								"""simple docstring"""
								__magic_name__		:DoubleLinkedList[T, U]   =   DoubleLinkedList()
								__magic_name__		:Dict   =   capacity
								__magic_name__		:Union[str, Any]   =   0
								__magic_name__		:Dict   =   0
								__magic_name__		:Optional[Any]   =   0
								__magic_name__		:dict[T, DoubleLinkedListNode[T, U]]   =   {}







				def __repr__(    self  ):
								"""simple docstring"""
								return (
								    F'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
								    F'''capacity={self.capacity}, current size={self.num_keys})'''
								)







				def __contains__(    self							,       __lowerCAmelCase  ):
								"""simple docstring"""
								return key in self.cache







				def       A						(    self							,       __lowerCAmelCase  ):
								"""simple docstring"""
								# Note: pythonic interface would throw KeyError rather than return None

								if key in self.cache:
												self.hits += 1
												__magic_name__		:DoubleLinkedListNode[T, U]   =   self.cache[key]
												__magic_name__		:int   =   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(__lowerCAmelCase  )
												return node.val
								self.miss += 1
								return None







				def       A						(    self							,       __lowerCAmelCase							,       __lowerCAmelCase  ):
								"""simple docstring"""

								if key not in self.cache:
												if self.num_keys >= self.capacity:
																# delete first node (oldest) when over capacity
																__magic_name__		:Union[str, Any]   =   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(__lowerCAmelCase  ) 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
												__magic_name__		:List[Any]   =   DoubleLinkedListNode(__lowerCAmelCase							,       __lowerCAmelCase  )
												self.list.add(self.cache[key]  )
												self.num_keys += 1

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







				@classmethod
				def       A						(    cls							,       __lowerCAmelCase = 1_2_8  ):
								"""simple docstring"""

								def cache_decorator_inner(__lowerCAmelCase  ) -> Callable[..., U]:
												def cache_decorator_wrapper(*__lowerCAmelCase  ) -> U:
																if func not in cls.decorator_function_to_instance_map:
																				__magic_name__		:List[str]   =   LRUCache(__lowerCAmelCase  )

																__magic_name__		:Optional[Any]   =   cls.decorator_function_to_instance_map[func].get(args[0]  )
																if result is None:
																				__magic_name__		:Optional[Any]   =   func(*__lowerCAmelCase  )
																				cls.decorator_function_to_instance_map[func].put(args[0]							,       __lowerCAmelCase  )
																return result

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

												setattr(__lowerCAmelCase							,       '''cache_info'''							,       __lowerCAmelCase  )  # noqa: B010

												return cache_decorator_wrapper

								return cache_decorator_inner


if __name__ == "__main__":
					import doctest

					doctest.testmod()













'''simple docstring'''




import enum
import shutil
import sys


a__      ,       a__					:			Any          =     shutil.get_terminal_size()

a__					:			Optional[int]          =     {'''UP''': '''A''', '''DOWN''': '''B''', '''RIGHT''': '''C''', '''LEFT''': '''D'''}






class 				__snake_case     (					enum.Enum							):
	__lowerCAmelCase       						=  0
	__lowerCAmelCase       						=  1





def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_=""							)   ->Optional[Any]:
	sys.stdout.write(str(UpperCAmelCase_							) + end							)
	sys.stdout.flush()




def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_=""							)   ->List[str]:
	forceWrite(f'''\u001b[{color}m{content}\u001b[0m'''					,				UpperCAmelCase_							)




def 						__lowerCamelCase			(	)   ->Optional[Any]:
	forceWrite('\r'							)




def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_							)   ->Any:
	forceWrite(f'''\033[{num_lines}{CURSOR_TO_CHAR[direction.upper()]}'''							)




def 						__lowerCamelCase			(	)   ->str:
	forceWrite(' ' * TERMINAL_WIDTH							)
	reset_cursor()







def 						__lowerCamelCase			(	)   ->Tuple:
	reset_cursor()
	forceWrite('-' * TERMINAL_WIDTH							)



