



from __future__ import annotations

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

UpperCAmelCase_									=							TypeVar("T")
UpperCAmelCase_									=							TypeVar("U")





class 		UpperCAmelCase						(						Generic[T, U]				):





   def __init__(	self       ,     _lowerCAmelCase       ,     _lowerCAmelCase			):
         _lowerCAmelCase 			=  key
         _lowerCAmelCase 			=  val
         _lowerCAmelCase 			=  None
         _lowerCAmelCase 			=  None





   def __repr__(	self			):
         return (
             F'''Node: key: {self.key}, val: {self.val}, '''
             F'''has next: {bool(self.next			)}, has prev: {bool(self.prev			)}'''
         )






class 		UpperCAmelCase						(						Generic[T, U]				):





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





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





   def 	__lowerCAmelCase							(	self       ,     _lowerCAmelCase			):
         _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 	__lowerCAmelCase							(	self       ,     _lowerCAmelCase			):

         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 		UpperCAmelCase						(						Generic[T, U]				):
   SCREAMING_SNAKE_CASE__							=     {}





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





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





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





   def 	__lowerCAmelCase							(	self       ,     _lowerCAmelCase			):
         # 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(_lowerCAmelCase			)
               return node.val
         self.miss += 1
         return None





   def 	__lowerCAmelCase							(	self       ,     _lowerCAmelCase       ,     _lowerCAmelCase			):

         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(_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
               _lowerCAmelCase 			=  DoubleLinkedListNode(_lowerCAmelCase       ,     _lowerCAmelCase			)
               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(_lowerCAmelCase			)





   @classmethod
   def 	__lowerCAmelCase							(	cls       ,     _lowerCAmelCase = 128			):

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

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




def 							UpperCAmelCase__		(				_SCREAMING_SNAKE_CASE   :	list[int]     ,				_SCREAMING_SNAKE_CASE   :	str				)->list[int]:
      _lowerCAmelCase 			=  int(_SCREAMING_SNAKE_CASE				)

      # Initialize Result
      _lowerCAmelCase 			=  []

      # Traverse through all denomination
      for denomination in reversed(_SCREAMING_SNAKE_CASE				):
            # Find denominations
            while int(_SCREAMING_SNAKE_CASE				) >= int(_SCREAMING_SNAKE_CASE				):
                  total_value -= int(_SCREAMING_SNAKE_CASE				)
                  answer.append(_SCREAMING_SNAKE_CASE				)  # Append the "answers" array

      return answer


# Driver Code
if __name__ == "__main__":
    UpperCAmelCase_									=							[]
    UpperCAmelCase_									=							"0"

    if (
        input("Do you want to enter your denominations ? (yY/n): ").strip().lower()
        == "y"
    ):
        UpperCAmelCase_									=							int(input("Enter the number of denominations you want to add: ").strip())

        for i in range(0, n):
            denominations.append(int(input(F"""Denomination {i}: """).strip()))
        UpperCAmelCase_									=							input("Enter the change you want to make in Indian Currency: ").strip()
    else:
        # All denominations of Indian Currency if user does not enter
        UpperCAmelCase_									=							[1, 2, 5, 1_0, 2_0, 5_0, 1_0_0, 5_0_0, 2_0_0_0]
        UpperCAmelCase_									=							input("Enter the change you want to make: ").strip()

    if int(value) == 0 or int(value) < 0:
        print("The total value cannot be zero or negative.")

    else:
        print(F"""Following is minimal change for {value}: """)
        UpperCAmelCase_									=							find_minimum_change(denominations, value)
        # Print result
        for i in range(len(answer)):
            print(answer[i], end=" ")