





from __future__ import annotations

import sys
from collections import deque
from typing import Generic, TypeVar

_A :   Optional[Any]  			=  TypeVar('T')


class        __SCREAMING_SNAKE_CASE      (			Generic[T] ):
       _UpperCAmelCase				:  deque[T]  # Cache store of keys
       _UpperCAmelCase				:  set[T]  # References of the keys in cache
       _UpperCAmelCase				:  int			   =   1_0  # Maximum capacity of cache







       def __init__(				self					:     Dict		, A					:     int      )       ->None:
          lowerCamelCase__       :						List[Any]        =							deque()
          lowerCamelCase__       :						Dict        =							set()
          if not n:
             lowerCamelCase__       :						List[Any]        =							sys.maxsize
          elif n < 0:
             raise ValueError('''n should be an integer greater than 0.'''      )
          else:
             lowerCamelCase__       :						Dict        =							n







       def 						__lowerCamelCase   (				self					:     int		, A					:     T      )       ->None:
          if x not in self.key_reference:
             if len(self.dq_store      ) == LRUCache._MAX_CAPACITY:
                lowerCamelCase__       :						Union[str, Any]        =							self.dq_store.pop()
                self.key_reference.remove(A      )
          else:
             self.dq_store.remove(A      )

          self.dq_store.appendleft(A      )
          self.key_reference.add(A      )







       def 						__lowerCamelCase   (				self					:     Union[str, Any]      )       ->None:
          for k in self.dq_store:
             print(A      )







       def __repr__(				self					:     Optional[Any]      )       ->str:
          return F"LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store      )}"


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       _A :   LRUCache[str | int]  			=  LRUCache(4)
       lru_cache.refer('A')
       lru_cache.refer(2)
       lru_cache.refer(3)
       lru_cache.refer('A')
       lru_cache.refer(4)
       lru_cache.refer(5)
       lru_cache.display()

       print(lru_cache)
       assert str(lru_cache) == "LRUCache(4) => [5, 4, 'A', 3]"










def 	_a						(   UpperCAmelCase					)    ->    int:







   """simple docstring"""
   if not isinstance(UpperCAmelCase      ,  UpperCAmelCase					) or number < 0:
      raise ValueError('''Input must be a non-negative integer'''					)

   lowerCamelCase__       :						List[str]        =							0
   while number:
      # This way we arrive at next set bit (next 1) instead of looping
      # through each bit and checking for 1s hence the
      # loop won't run 32 times it will only run the number of `1` times
      number &= number - 1
      count += 1
   return count


if __name__ == "__main__":
       import doctest

       doctest.testmod()



