

from __future__ import annotations

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

UpperCamelCase__     :					str								=			TypeVar("T")
UpperCamelCase__     :					str								=			TypeVar("U")



class 					__snake_case     (			Generic[T, U]				):

  def __init__(    self  ,						_A  ,						_A):
      SCREAMING_SNAKE_CASE_													=  key
      SCREAMING_SNAKE_CASE_													=  val
      SCREAMING_SNAKE_CASE_													=  0
      SCREAMING_SNAKE_CASE_													=  None
      SCREAMING_SNAKE_CASE_													=  None


  def __repr__(    self):
      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 					__snake_case     (			Generic[T, U]				):

  def __init__(    self):
      SCREAMING_SNAKE_CASE_													=  DoubleLinkedListNode(_A  ,						_A)
      SCREAMING_SNAKE_CASE_													=  DoubleLinkedListNode(_A  ,						_A)
      SCREAMING_SNAKE_CASE_							,	SCREAMING_SNAKE_CASE_													=  self.rear, self.head

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

  def   lowerCAmelCase__   (    self  ,						_A):
      SCREAMING_SNAKE_CASE_													=  self.rear.prev

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

      SCREAMING_SNAKE_CASE_													=  node
      SCREAMING_SNAKE_CASE_													=  previous
      SCREAMING_SNAKE_CASE_													=  node
      SCREAMING_SNAKE_CASE_													=  self.rear
      node.freq += 1
      self._position_node(_A)

  def   lowerCAmelCase__   (    self  ,						_A):

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

          SCREAMING_SNAKE_CASE_													=  previous_node.prev
          SCREAMING_SNAKE_CASE_													=  node.prev
          SCREAMING_SNAKE_CASE_													=  previous_node
          SCREAMING_SNAKE_CASE_													=  node


  def   lowerCAmelCase__   (    self  ,						_A):

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

      SCREAMING_SNAKE_CASE_													=  node.next
      SCREAMING_SNAKE_CASE_													=  node.prev
      SCREAMING_SNAKE_CASE_													=  None
      SCREAMING_SNAKE_CASE_													=  None
      return node






class 					__snake_case     (			Generic[T, U]				):
  __lowerCAmelCase   :		dict[Callable[[T], U], LFUCache[T, U]]         =     {}

  def __init__(    self  ,						_A):
      SCREAMING_SNAKE_CASE_													=  DoubleLinkedList()
      SCREAMING_SNAKE_CASE_													=  capacity
      SCREAMING_SNAKE_CASE_													=  0
      SCREAMING_SNAKE_CASE_													=  0
      SCREAMING_SNAKE_CASE_													=  0
      SCREAMING_SNAKE_CASE_													=  {}

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

  def __contains__(    self  ,						_A):
      return key in self.cache

  def   lowerCAmelCase__   (    self  ,						_A):

      if key in self.cache:
          self.hits += 1
          SCREAMING_SNAKE_CASE_													=  self.cache[key]
          SCREAMING_SNAKE_CASE_													=  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   lowerCAmelCase__   (    self  ,						_A  ,						_A):

      if key not in self.cache:
          if self.num_keys >= self.capacity:
              # delete first node when over capacity
              SCREAMING_SNAKE_CASE_													=  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
          SCREAMING_SNAKE_CASE_													=  DoubleLinkedListNode(_A  ,						_A)
          self.list.add(self.cache[key])
          self.num_keys += 1

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


  @classmethod
  def   lowerCAmelCase__   (    cls  ,						_A = 128):

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

              SCREAMING_SNAKE_CASE_													=  cls.decorator_function_to_instance_map[func].get(args[0])
              if result is None:
                  SCREAMING_SNAKE_CASE_													=  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()





from itertools import permutations


def     _UpperCAmelCase				(     ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  list(map(''.join       ,      permutations('0123456789'				)				)				)
    return result[999_999]


if __name__ == "__main__":
       print(solution())


