


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

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

__SCREAMING_SNAKE_CASE				:							Any		       =		TypeVar('''T''')
__SCREAMING_SNAKE_CASE				:							str		       =		TypeVar('''U''')






class 				__lowerCAmelCase      (      Generic[T, U]	):

						"""simple docstring"""






						def __init__(     self       :			List[str]   ,     lowerCAmelCase       :			int   ,     lowerCAmelCase       :			Optional[Any]  ):
													A_ 						=		key
													A_ 						=		val
													A_ 						=		0
													A_ 						=		None
													A_ 						=		None






						def __repr__(     self       :			Tuple  ):
													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       :			Tuple  ):
													A_ 						=		DoubleLinkedListNode(a_   ,     a_  )
													A_ 						=		DoubleLinkedListNode(a_   ,     a_  )
													A_						,				A_ 						=		self.rear, self.head






						def __repr__(     self       :			Union[str, Any]  ):
													A_ 						=		["DoubleLinkedList"]
													A_ 						=		self.head
													while node.next is not None:
																				rep.append(str(a_  )  )
																				A_ 						=		node.next
													rep.append(str(self.rear  )  )
													return ",\n    ".join(a_  )






						def 							_UpperCAmelCase					(     self       :			Optional[int]   ,     lowerCAmelCase       :			Any  ):
													A_ 						=		self.rear.prev

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

													A_ 						=		node
													A_ 						=		previous
													A_ 						=		node
													A_ 						=		self.rear
													node.freq += 1
													self._position_node(a_  )






						def 							_UpperCAmelCase					(     self       :			str   ,     lowerCAmelCase       :			str  ):

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

																				A_ 						=		previous_node.prev
																				A_ 						=		node.prev
																				A_ 						=		previous_node
																				A_ 						=		node






						def 							_UpperCAmelCase					(     self       :			Tuple   ,     lowerCAmelCase       :			Union[str, Any]  ):

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

													A_ 						=		node.next
													A_ 						=		node.prev
													A_ 						=		None
													A_ 						=		None
													return node






class 				__lowerCAmelCase      (      Generic[T, U]	):

						"""simple docstring"""






						_UpperCAmelCase		:					dict[Callable[[T], U], LFUCache[T, U]]      	=	{}






						def __init__(     self       :			Optional[Any]   ,     lowerCAmelCase       :			Tuple  ):
													A_ 						=		DoubleLinkedList()
													A_ 						=		capacity
													A_ 						=		0
													A_ 						=		0
													A_ 						=		0
													A_ 						=		{}






						def __repr__(     self       :			str  ):
													return (
													    F"CacheInfo(hits={self.hits}, misses={self.miss}, "
													    F"capacity={self.capacity}, current_size={self.num_keys})"
													)






						def __contains__(     self       :			Tuple   ,     lowerCAmelCase       :			str  ):
													return key in self.cache






						def 							_UpperCAmelCase					(     self       :			Dict   ,     lowerCAmelCase       :			str  ):

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






						def 							_UpperCAmelCase					(     self       :			Any   ,     lowerCAmelCase       :			int   ,     lowerCAmelCase       :			List[str]  ):

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

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

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






						@classmethod
						def 							_UpperCAmelCase					(     cls       :			Optional[int]   ,     lowerCAmelCase       :			Dict = 1_28  ):

													def cache_decorator_inner(lowerCAmelCase       :			Dict  ) -> Callable[..., U]:
																				def cache_decorator_wrapper(*lowerCAmelCase       :			Any  ) -> U:
																											if func not in cls.decorator_function_to_instance_map:
																																		A_ 						=		LFUCache(a_  )

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

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

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

																				return cache_decorator_wrapper

													return cache_decorator_inner


if __name__ == "__main__":
							import doctest

							doctest.testmod()









'''simple docstring'''
def 			a_							(  UpperCamelCase_	,     UpperCamelCase_ = 1_0_0_0   ):
							if (not isinstance(UpperCamelCase_	,     UpperCamelCase_   )) or (digit_position <= 0):
														raise ValueError("Digit position must be a positive integer"   )
							elif (not isinstance(UpperCamelCase_	,     UpperCamelCase_   )) or (precision < 0):
														raise ValueError("Precision must be a nonnegative integer"   )

							# compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly
							# accurate
							A_ 						=		(
							    4 * _subsum(UpperCamelCase_	,     1	,     UpperCamelCase_   )
							    - 2 * _subsum(UpperCamelCase_	,     4	,     UpperCamelCase_   )
							    - _subsum(UpperCamelCase_	,     5	,     UpperCamelCase_   )
							    - _subsum(UpperCamelCase_	,     6	,     UpperCamelCase_   )
							)

							# return the first hex digit of the fractional part of the result
							return hex(int((sum_result % 1) * 1_6   )   )[2:]







def 			a_							(  UpperCamelCase_	,     UpperCamelCase_	,     UpperCamelCase_   ):
							A_ 						=		0.0
							for sum_index in range(digit_pos_to_extract + precision   ):
														A_ 						=		8 * sum_index + denominator_addend
														if sum_index < digit_pos_to_extract:
																					# if the exponential term is an integer and we mod it by the denominator
																					# before dividing, only the integer part of the sum will change;
																					# the fractional part will not
																					A_ 						=		pow(
																					    1_6	,     digit_pos_to_extract - 1 - sum_index	,     UpperCamelCase_   )
														else:
																					A_ 						=		pow(1_6	,     digit_pos_to_extract - 1 - sum_index   )
														total += exponential_term / denominator
							return total


if __name__ == "__main__":
							import doctest

							doctest.testmod()





