





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

__UpperCamelCase:	Union[str, Any] = TypeVar("""KEY""")
__UpperCamelCase:	Dict = TypeVar("""VAL""")


@dataclass(frozen=_UpperCamelCase   ,    slots=_UpperCamelCase      )
class       __lowerCAmelCase					(       Generic[KEY, VAL]      ):


	'''simple docstring'''





	_A													=				42
	_A													=				42


class       __lowerCAmelCase					(       _Item      ):


	'''simple docstring'''





	def __init__(						self:						int			):
			super().__init__(lowerCamelCase_,					lowerCamelCase_			)





	def __bool__(						self:						str			):
			return False
__UpperCamelCase:	Optional[int] = _DeletedItem()


class       __lowerCAmelCase					(       MutableMapping[KEY, VAL]      ):


	'''simple docstring'''





	def __init__(						self:						Dict,					lowerCamelCase_:						int = 8,					lowerCamelCase_:						float = 0.7_5			):
			lowercase__					:      Optional[Any]      =		initial_block_size
			lowercase__					:      list[_Item | None]      =		[None] * initial_block_size
			assert 0.0 < capacity_factor < 1.0
			lowercase__					:      str      =		capacity_factor
			lowercase__					:      Tuple      =		0

	def    snake_case__(						self:						Tuple,					lowerCamelCase_:						KEY			):
			return hash(lowerCamelCase_			) % len(self._buckets			)

	def    snake_case__(						self:						Optional[Any],					lowerCamelCase_:						int			):
			return (ind + 1) % len(self._buckets			)

	def    snake_case__(						self:						Optional[Any],					lowerCamelCase_:						int,					lowerCamelCase_:						KEY,					lowerCamelCase_:						VAL			):
			lowercase__					:      Dict      =		self._buckets[ind]
			if not stored:
					lowercase__					:      Optional[Any]      =		_Item(lowerCamelCase_,					lowerCamelCase_			)
					self._len += 1
					return True
			elif stored.key == key:
					lowercase__					:      Optional[Any]      =		_Item(lowerCamelCase_,					lowerCamelCase_			)
					return True
			else:
					return False

	def    snake_case__(						self:						Union[str, Any]			):
			lowercase__					:      List[Any]      =		len(self._buckets			) * self._capacity_factor
			return len(self			) >= int(lowerCamelCase_			)

	def    snake_case__(						self:						Union[str, Any]			):
			if len(self._buckets			) <= self._initial_block_size:
					return False
			lowercase__					:      List[Any]      =		len(self._buckets			) * self._capacity_factor / 2
			return len(self			) < limit

	def    snake_case__(						self:						Union[str, Any],					lowerCamelCase_:						int			):
			lowercase__					:      str      =		self._buckets
			lowercase__					:      List[str]      =		[None] * new_size
			lowercase__					:      Tuple      =		0
			for item in old_buckets:
					if item:
							self._add_item(item.key,					item.val			)

	def    snake_case__(						self:						List[Any]			):
			self._resize(len(self._buckets			) * 2			)

	def    snake_case__(						self:						int			):
			self._resize(len(self._buckets			) // 2			)

	def    snake_case__(						self:						Optional[Any],					lowerCamelCase_:						KEY			):
			lowercase__					:      List[Any]      =		self._get_bucket_index(lowerCamelCase_			)
			for _ in range(len(self._buckets			)			):
					yield ind
					lowercase__					:      Optional[Any]      =		self._get_next_ind(lowerCamelCase_			)

	def    snake_case__(						self:						List[str],					lowerCamelCase_:						KEY,					lowerCamelCase_:						VAL			):
			for ind in self._iterate_buckets(lowerCamelCase_			):
					if self._try_set(lowerCamelCase_,					lowerCamelCase_,					lowerCamelCase_			):
							break

	def __setitem__(						self:						Tuple,					lowerCamelCase_:						KEY,					lowerCamelCase_:						VAL			):
			if self._is_full():
					self._size_up()

			self._add_item(lowerCamelCase_,					lowerCamelCase_			)

	def __delitem__(						self:						Optional[Any],					lowerCamelCase_:						KEY			):
			for ind in self._iterate_buckets(lowerCamelCase_			):
					lowercase__					:      Tuple      =		self._buckets[ind]
					if item is None:
							raise KeyError(lowerCamelCase_			)
					if item is _deleted:
							continue
					if item.key == key:
							lowercase__					:      Dict      =		_deleted
							self._len -= 1
							break
			if self._is_sparse():
					self._size_down()

	def __getitem__(						self:						Any,					lowerCamelCase_:						KEY			):
			for ind in self._iterate_buckets(lowerCamelCase_			):
					lowercase__					:      List[str]      =		self._buckets[ind]
					if item is None:
							break
					if item is _deleted:
							continue
					if item.key == key:
							return item.val
			raise KeyError(lowerCamelCase_			)

	def __len__(						self:						Optional[int]			):
			return self._len

	def __iter__(						self:						Union[str, Any]			):
			yield from (item.key for item in self._buckets if item)





	def __repr__(						self:						int			):
			lowercase__					:      Union[str, Any]      =		' ,'.join(
			    F"""{item.key}: {item.val}""" for item in self._buckets if item			)
			return F"""HashMap({val_string})"""









def       SCREAMING_SNAKE_CASE__  (       _lowercase     : str			)   ->							str:




		'''simple docstring'''
		if not all(char in '01' for char in bin_string			):
				raise ValueError('Non-binary value was passed to the function'			)
		if not bin_string:
				raise ValueError('Empty string was passed to the function'			)
		lowercase__					:      Tuple      =		''
		while len(_lowercase			) % 3 != 0:
				lowercase__					:      Optional[int]      =		'0' + bin_string
		lowercase__					:      List[Any]      =		[
		    bin_string[index : index + 3]
		    for index in range(len(_lowercase			)			)
		    if index % 3 == 0
		]
		for bin_group in bin_string_in_3_list:
				lowercase__					:      int      =		0
				for index, val in enumerate(_lowercase			):
						oct_val += int(2 ** (2 - index) * int(_lowercase			)			)
				oct_string += str(_lowercase			)
		return oct_string


if __name__ == "__main__":
			from doctest import testmod

			testmod()


