

from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

lowerCAmelCase     :   List[str]						     =  TypeVar('KEY')
lowerCAmelCase     :   Optional[int]						     =  TypeVar('VAL')
@dataclass(frozen=_UpperCamelCase   ,     slots=_UpperCamelCase)
class  _A		(  Generic[KEY, VAL]):
  SCREAMING_SNAKE_CASE    :      KEY
  SCREAMING_SNAKE_CASE    :      VAL

class  _A		(  _Item):

  def __init__(				self					):





        """simple docstring"""







        super().__init__(__a ,					__a					)



  def __bool__(				self					):





        """simple docstring"""







        return False

lowerCAmelCase     :   Optional[Any]						     =  _DeletedItem()
class  _A		(  MutableMapping[KEY, VAL]):

  def __init__(				self ,					_SCREAMING_SNAKE_CASE = 8 ,					_SCREAMING_SNAKE_CASE = 0.75					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  str           =     initial_block_size
        SCREAMING_SNAKE_CASE_				:  list[_Item | None]           =     [None] * initial_block_size
        assert 0.0 < capacity_factor < 1.0
        SCREAMING_SNAKE_CASE_				:  List[str]           =     capacity_factor
        SCREAMING_SNAKE_CASE_				:  Dict           =     0

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        return hash(__a					) % len(self._buckets					)

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        return (ind + 1) % len(self._buckets					)

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE ,					_SCREAMING_SNAKE_CASE ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  List[Any]           =     self._buckets[ind]
        if not stored:
              SCREAMING_SNAKE_CASE_				:  Tuple           =     _Item(__a ,					__a					)
              self._len += 1
              return True
        elif stored.key == key:
              SCREAMING_SNAKE_CASE_				:  Union[str, Any]           =     _Item(__a ,					__a					)
              return True
        else:
              return False

  def  UpperCAmelCase    (				self					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  Any           =     len(self._buckets					) * self._capacity_factor
        return len(self					) >= int(__a					)

  def  UpperCAmelCase    (				self					):





        """simple docstring"""







        if len(self._buckets					) <= self._initial_block_size:
              return False
        SCREAMING_SNAKE_CASE_				:  List[str]           =     len(self._buckets					) * self._capacity_factor / 2
        return len(self					) < limit

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  Any           =     self._buckets
        SCREAMING_SNAKE_CASE_				:  List[Any]           =     [None] * new_size
        SCREAMING_SNAKE_CASE_				:  List[str]           =     0
        for item in old_buckets:
              if item:
                    self._add_item(item.key ,					item.val					)

  def  UpperCAmelCase    (				self					):





        """simple docstring"""







        self._resize(len(self._buckets					) * 2					)

  def  UpperCAmelCase    (				self					):





        """simple docstring"""







        self._resize(len(self._buckets					) // 2					)

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  str           =     self._get_bucket_index(__a					)
        for _ in range(len(self._buckets					)					):
              yield ind
              SCREAMING_SNAKE_CASE_				:  Tuple           =     self._get_next_ind(__a					)

  def  UpperCAmelCase    (				self ,					_SCREAMING_SNAKE_CASE ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        for ind in self._iterate_buckets(__a					):
              if self._try_set(__a ,					__a ,					__a					):
                    break

  def __setitem__(				self ,					_SCREAMING_SNAKE_CASE ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        if self._is_full():
              self._size_up()

        self._add_item(__a ,					__a					)

  def __delitem__(				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        for ind in self._iterate_buckets(__a					):
              SCREAMING_SNAKE_CASE_				:  Tuple           =     self._buckets[ind]
              if item is None:
                    raise KeyError(__a					)
              if item is _deleted:
                    continue
              if item.key == key:
                    SCREAMING_SNAKE_CASE_				:  List[Any]           =     _deleted
                    self._len -= 1
                    break
        if self._is_sparse():
              self._size_down()

  def __getitem__(				self ,					_SCREAMING_SNAKE_CASE					):





        """simple docstring"""







        for ind in self._iterate_buckets(__a					):
              SCREAMING_SNAKE_CASE_				:  Tuple           =     self._buckets[ind]
              if item is None:
                    break
              if item is _deleted:
                    continue
              if item.key == key:
                    return item.val
        raise KeyError(__a					)

  def __len__(				self					):





        """simple docstring"""







        return self._len

  def __iter__(				self					):





        """simple docstring"""







        yield from (item.key for item in self._buckets if item)



  def __repr__(				self					):





        """simple docstring"""







        SCREAMING_SNAKE_CASE_				:  Optional[int]           =     " ,".join(
            f"{item.key}: {item.val}" for item in self._buckets if item					)
        return f"HashMap({val_string})"









def    A_  (							a  ):

      """simple docstring"""



      SCREAMING_SNAKE_CASE_				:  List[Any]           =     0
      while num > 0:
            digit_sum += num % 1_0
            num //= 1_0
      return digit_sum

def    A_  (							a = 1_0_0  ):

      """simple docstring"""



      SCREAMING_SNAKE_CASE_				:  List[str]           =     1
      SCREAMING_SNAKE_CASE_				:  Union[str, Any]           =     2

      for i in range(2					,   max_n + 1  ):
            SCREAMING_SNAKE_CASE_				:  List[str]           =     pre_numerator
            SCREAMING_SNAKE_CASE_				:  str           =     2 * i // 3 if i % 3 == 0 else 1
            SCREAMING_SNAKE_CASE_				:  Tuple           =     cur_numerator
            SCREAMING_SNAKE_CASE_				:  Tuple           =     e_cont * pre_numerator + temp

      return sum_digits(a  )


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






