






from __future__ import annotations

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

_a   			=						TypeVar('''T''')
_a   			=						TypeVar('''U''')





class __lowerCamelCase				(   Generic[T, U]):





	"""simple docstring"""






	def __init__(							self ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    key
							_UpperCAmelCase             =    val
							_UpperCAmelCase             =    0
							_UpperCAmelCase             =    None
							_UpperCAmelCase             =    None

	def __repr__(							self					):
							"""simple docstring"""







							return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
							    self.key ,					self.val ,					self.freq ,					self.next is not None ,					self.prev is not None					)





class __lowerCamelCase				(   Generic[T, U]):





	"""simple docstring"""






	def __init__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    DoubleLinkedListNode(UpperCAmelCase ,					UpperCAmelCase					)
							_UpperCAmelCase             =    DoubleLinkedListNode(UpperCAmelCase ,					UpperCAmelCase					)
							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.rear, self.head

	def __repr__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    ['DoubleLinkedList']
							_UpperCAmelCase             =    self.head
							while node.next is not None:
													rep.append(str(UpperCAmelCase					)					)
													_UpperCAmelCase             =    node.next
							rep.append(str(self.rear					)					)
							return ",\n    ".join(UpperCAmelCase					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.rear.prev

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

							_UpperCAmelCase             =    node
							_UpperCAmelCase             =    previous
							_UpperCAmelCase             =    node
							_UpperCAmelCase             =    self.rear
							node.freq += 1
							self._position_node(UpperCAmelCase					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							while node.prev is not None and node.prev.freq > node.freq:
													# swap node with previous node
													_UpperCAmelCase             =    node.prev

													_UpperCAmelCase             =    previous_node.prev
													_UpperCAmelCase             =    node.prev
													_UpperCAmelCase             =    previous_node
													_UpperCAmelCase             =    node

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







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

							_UpperCAmelCase             =    node.next
							_UpperCAmelCase             =    node.prev
							_UpperCAmelCase             =    None
							_UpperCAmelCase             =    None
							return node





class __lowerCamelCase				(   Generic[T, U]):





	"""simple docstring"""






	UpperCamelCase__			=   {}

	def __init__(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    DoubleLinkedList()
							_UpperCAmelCase             =    capacity
							_UpperCAmelCase             =    0
							_UpperCAmelCase             =    0
							_UpperCAmelCase             =    0
							_UpperCAmelCase             =    {}

	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 ,					UpperCAmelCase					):
							"""simple docstring"""







							return key in self.cache

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							if key in self.cache:
													self.hits += 1
													_UpperCAmelCase             =    self.cache[key]
													_UpperCAmelCase             =    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(UpperCAmelCase					)
													return node.val
							self.miss += 1
							return None

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							if key not in self.cache:
													if self.num_keys >= self.capacity:
																			# delete first node when over capacity
																			_UpperCAmelCase             =    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(UpperCAmelCase					) is not None
																			# first_node guaranteed to be in list

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

							else:
													_UpperCAmelCase             =    self.list.remove(self.cache[key]					)
													assert node is not None  # node guaranteed to be in list
													_UpperCAmelCase             =    value
													self.list.add(UpperCAmelCase					)

	@classmethod
	def  UpperCamelCase					(							cls ,					UpperCAmelCase = 128					):
							"""simple docstring"""







							def cache_decorator_inner(UpperCAmelCase					) -> Callable[..., U]:
													def cache_decorator_wrapper(*UpperCAmelCase					) -> U:
																			if func not in cls.decorator_function_to_instance_map:
																									_UpperCAmelCase             =    LFUCache(UpperCAmelCase					)

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

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

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

													return cache_decorator_wrapper

							return cache_decorator_inner


if __name__ == "__main__":
		import doctest

		doctest.testmod()








from itertools import combinations_with_replacement


def __A					(   __lowerCAmelCase = 100			)->						int:





						"""simple docstring"""



						_UpperCAmelCase             =    [*list(range(1				,	21			)			), 25]
						_UpperCAmelCase             =    [2 * x for x in range(1				,	21			)] + [50]
						_UpperCAmelCase             =    [3 * x for x in range(1				,	21			)]
						_UpperCAmelCase             =    singles + doubles + triples + [0]

						_UpperCAmelCase             =    0
						_UpperCAmelCase             =    42
						_UpperCAmelCase             =    42
						_UpperCAmelCase             =    42
						_UpperCAmelCase             =    42

						for double in doubles:
												for throwa, throwa in combinations_with_replacement(__lowerCAmelCase				,	2			):
																		_UpperCAmelCase             =    double + throwa + throwa
																		if checkout_total < limit:
																								num_checkouts += 1

						return num_checkouts


if __name__ == "__main__":
		print(F'''{solution() = }''')
