



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

A_		:     Any        =     TypeVar('''KEY''')
A_		:     Any        =     TypeVar('''VAL''')



@dataclass(frozen=UpperCAmelCase_,   slots=UpperCAmelCase_	)
class 		_lowercase		(       Generic[KEY, VAL]	):
   _UpperCAmelCase     	=			42
   _UpperCAmelCase     	=			42



class 		_lowercase		(       _Item	):

   def __init__(      self			:       int							)       ->				Any:


    """simple docstring"""






    super().__init__(_snake_case							,   _snake_case							)




   def __bool__(      self			:       List[str]							)       ->				Optional[Any]:


    """simple docstring"""






    return False

A_		:     Optional[Any]        =     _DeletedItem()



class 		_lowercase		(       MutableMapping[KEY, VAL]	):

   def __init__(      self			:       List[Any]							,   __lowerCAmelCase			:       int = 8							,   __lowerCAmelCase			:       float = 0.7_5							)       ->				Tuple:


    """simple docstring"""






    a						=		initial_block_size
    a						=		[None] * initial_block_size
    assert 0.0 < capacity_factor < 1.0
    a						=		capacity_factor
    a						=		0

   def 		A							(      self			:       Dict							,   __lowerCAmelCase			:       KEY							)       ->				Optional[int]:


    """simple docstring"""






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

   def 		A							(      self			:       Optional[Any]							,   __lowerCAmelCase			:       int							)       ->				List[str]:


    """simple docstring"""






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

   def 		A							(      self			:       Any							,   __lowerCAmelCase			:       int							,   __lowerCAmelCase			:       KEY							,   __lowerCAmelCase			:       VAL							)       ->				List[Any]:


    """simple docstring"""






    a						=		self._buckets[ind]
    if not stored:
     a						=		_Item(_snake_case							,   _snake_case							)
     self._len += 1
     return True
    elif stored.key == key:
     a						=		_Item(_snake_case							,   _snake_case							)
     return True
    else:
     return False

   def 		A							(      self			:       List[Any]							)       ->				Optional[Any]:


    """simple docstring"""






    a						=		len(self._buckets							) * self._capacity_factor
    return len(self							) >= int(_snake_case							)

   def 		A							(      self			:       Optional[int]							)       ->				Optional[Any]:


    """simple docstring"""






    if len(self._buckets							) <= self._initial_block_size:
     return False
    a						=		len(self._buckets							) * self._capacity_factor / 2
    return len(self							) < limit

   def 		A							(      self			:       List[Any]							,   __lowerCAmelCase			:       int							)       ->				Optional[Any]:


    """simple docstring"""






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

   def 		A							(      self			:       Optional[Any]							)       ->				str:


    """simple docstring"""






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

   def 		A							(      self			:       Dict							)       ->				str:


    """simple docstring"""






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

   def 		A							(      self			:       str							,   __lowerCAmelCase			:       KEY							)       ->				Tuple:


    """simple docstring"""






    a						=		self._get_bucket_index(_snake_case							)
    for _ in range(len(self._buckets							)							):
     yield ind
     a						=		self._get_next_ind(_snake_case							)

   def 		A							(      self			:       Any							,   __lowerCAmelCase			:       KEY							,   __lowerCAmelCase			:       VAL							)       ->				Union[str, Any]:


    """simple docstring"""






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

   def __setitem__(      self			:       Union[str, Any]							,   __lowerCAmelCase			:       KEY							,   __lowerCAmelCase			:       VAL							)       ->				Tuple:


    """simple docstring"""






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

    self._add_item(_snake_case							,   _snake_case							)

   def __delitem__(      self			:       List[str]							,   __lowerCAmelCase			:       KEY							)       ->				Union[str, Any]:


    """simple docstring"""






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

   def __getitem__(      self			:       List[Any]							,   __lowerCAmelCase			:       KEY							)       ->				int:


    """simple docstring"""






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

   def __len__(      self			:       Any							)       ->				str:


    """simple docstring"""






    return self._len

   def __iter__(      self			:       List[str]							)       ->				List[str]:


    """simple docstring"""






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




   def __repr__(      self			:       Optional[int]							)       ->				Dict:


    """simple docstring"""






    a						=		" ,".join(
        f"""{item.key}: {item.val}""" for item in self._buckets if item							)
    return f"""HashMap({val_string})"""






def 	UpperCAmelCase__      (      UpperCAmelCase__ :Any					):






 '''simple docstring'''

 if not head:
  return True
 # split the list to two parts
 a		,  a						=		head.next, head
 while fast and fast.next:
  a						=		fast.next.next
  a						=		slow.next
 a						=		slow.next
 a						=		None  # Don't forget here! But forget still works!
 # reverse the second part
 a						=		None
 while second:
  a						=		second.next
  a						=		node
  a						=		second
  a						=		nxt
 # compare two parts
 # second part has the same or one less node
 while node:
  if node.val != head.val:
   return False
  a						=		node.next
  a						=		head.next
 return True


def 	UpperCAmelCase__      (      UpperCAmelCase__ :str					):






 '''simple docstring'''

 if not head or not head.next:
  return True

 # 1. Get the midpoint (slow)
 a						=		a						=		a						=		head
 while fast and fast.next:
  a		,  a						=		fast.next.next, slow.next

 # 2. Push the second half into the stack
 a						=		[slow.val]
 while slow.next:
  a						=		slow.next
  stack.append(slow.val					)

 # 3. Comparison
 while stack:
  if stack.pop() != cur.val:
   return False
  a						=		cur.next

 return True




def 	UpperCAmelCase__      (      UpperCAmelCase__ :Any					):






 '''simple docstring'''

 if not head or not head.next:
  return True
 a						=		{}
 a						=		0
 while head:
  if head.val in d:
   d[head.val].append(UpperCAmelCase__					)
  else:
   a						=		[pos]
  a						=		head.next
  pos += 1
 a						=		pos - 1
 a						=		0
 for v in d.values():
  if len(UpperCAmelCase__					) % 2 != 0:
   middle += 1
  else:
   a						=		0
   for i in range(0 ,					len(UpperCAmelCase__					)					):
    if v[i] + v[len(UpperCAmelCase__					) - 1 - step] != checksum:
     return False
    step += 1
  if middle > 1:
   return False
 return True

