





"""simple docstring"""






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

A			      =	TypeVar('''KEY''')
A			      =	TypeVar('''VAL''')




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







					'''simple docstring'''




					__lowerCAmelCase	=	42
					__lowerCAmelCase	=	42






class 					__lowercase      (      _Item				):







					'''simple docstring'''




					def __init__(    self  ):
									super().__init__(_UpperCAmelCase						,      _UpperCAmelCase  )







					def __bool__(    self  ):
									return False






A			      =	_DeletedItem()




class 					__lowercase      (      MutableMapping[KEY, VAL]				):







					'''simple docstring'''




					def __init__(    self						,      _UpperCAmelCase = 8						,      _UpperCAmelCase = 0.7_5  ):
									__a			:    Union[str, Any]      							=	initial_block_size
									__a			:    list[_Item | None]      							=	[None] * initial_block_size
									assert 0.0 < capacity_factor < 1.0
									__a			:    Optional[Any]      							=	capacity_factor
									__a			:    Union[str, Any]      							=	0







					def 			_lowerCamelCase		(    self						,      _UpperCAmelCase  ):
									return hash(_UpperCAmelCase  ) % len(self._buckets  )







					def 			_lowerCamelCase		(    self						,      _UpperCAmelCase  ):
									return (ind + 1) % len(self._buckets  )







					def 			_lowerCamelCase		(    self						,      _UpperCAmelCase						,      _UpperCAmelCase						,      _UpperCAmelCase  ):
									__a			:    List[str]      							=	self._buckets[ind]
									if not stored:
													__a			:    int      							=	_Item(_UpperCAmelCase						,      _UpperCAmelCase  )
													self._len += 1
													return True
									elif stored.key == key:
													__a			:    Dict      							=	_Item(_UpperCAmelCase						,      _UpperCAmelCase  )
													return True
									else:
													return False







					def 			_lowerCamelCase		(    self  ):
									__a			:    Optional[int]      							=	len(self._buckets  ) * self._capacity_factor
									return len(self  ) >= int(_UpperCAmelCase  )







					def 			_lowerCamelCase		(    self  ):
									if len(self._buckets  ) <= self._initial_block_size:
													return False
									__a			:    Optional[Any]      							=	len(self._buckets  ) * self._capacity_factor / 2
									return len(self  ) < limit







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







					def 			_lowerCamelCase		(    self  ):
									self._resize(len(self._buckets  ) * 2  )







					def 			_lowerCamelCase		(    self  ):
									self._resize(len(self._buckets  ) // 2  )







					def 			_lowerCamelCase		(    self						,      _UpperCAmelCase  ):
									__a			:    int      							=	self._get_bucket_index(_UpperCAmelCase  )
									for _ in range(len(self._buckets  )  ):
													yield ind
													__a			:    Dict      							=	self._get_next_ind(_UpperCAmelCase  )







					def 			_lowerCamelCase		(    self						,      _UpperCAmelCase						,      _UpperCAmelCase  ):
									for ind in self._iterate_buckets(_UpperCAmelCase  ):
													if self._try_set(_UpperCAmelCase						,      _UpperCAmelCase						,      _UpperCAmelCase  ):
																	break







					def __setitem__(    self						,      _UpperCAmelCase						,      _UpperCAmelCase  ):
									if self._is_full():
													self._size_up()

									self._add_item(_UpperCAmelCase						,      _UpperCAmelCase  )







					def __delitem__(    self						,      _UpperCAmelCase  ):
									for ind in self._iterate_buckets(_UpperCAmelCase  ):
													__a			:    List[str]      							=	self._buckets[ind]
													if item is None:
																	raise KeyError(_UpperCAmelCase  )
													if item is _deleted:
																	continue
													if item.key == key:
																	__a			:    Dict      							=	_deleted
																	self._len -= 1
																	break
									if self._is_sparse():
													self._size_down()







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







					def __len__(    self  ):
									return self._len







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







					def __repr__(    self  ):
									__a			:    List[str]      							=	''' ,'''.join(
									    f"""{item.key}: {item.val}""" for item in self._buckets if item  )
									return f"""HashMap({val_string})"""






'''simple docstring'''




import mpmath  # for roots of unity
import numpy as np


class 					SCREAMING_SNAKE_CASE       :


     def __init__(		self		,      _UpperCAmelCase=None		,      _UpperCAmelCase=None):

          '''simple docstring'''






          __A		:					List[Any]						=			list(poly_a or [0])[:]
          __A		:					Optional[int]						=			list(poly_b or [0])[:]

          # Remove leading zero coefficients
          while self.polyA[-1] == 0:
               self.polyA.pop()
          __A		:					Union[str, Any]						=			len(self.polyA)

          while self.polyB[-1] == 0:
               self.polyB.pop()
          __A		:					Optional[int]						=			len(self.polyB)

          # Add 0 to make lengths equal a power of 2
          __A		:					Optional[Any]						=			int(
              2 ** np.ceil(np.loga(len(self.polyA) + len(self.polyB) - 1)))

          while len(self.polyA) < self.c_max_length:
               self.polyA.append(0)
          while len(self.polyB) < self.c_max_length:
               self.polyB.append(0)
          # A complex root used for the fourier transform
          __A		:					str						=			complex(mpmath.root(x=1		,      n=self.c_max_length		,      k=1))

          # The product
          __A		:					Tuple						=			self.__multiply()


     def 				SCREAMING_SNAKE_CASE    (		self		,      _UpperCAmelCase):

          '''simple docstring'''






          __A		:					Optional[int]						=			[[x] for x in self.polyA] if which == 'A' else [[x] for x in self.polyB]
          # Corner case
          if len(_UpperCAmelCase) <= 1:
               return dft[0]
          #
          __A		:					Dict						=			self.c_max_length // 2
          while next_ncol > 0:
               __A		:					Optional[Any]						=			[[] for i in range(_UpperCAmelCase)]
               __A		:					Tuple						=			self.root**next_ncol

               # First half of next step
               __A		:					Optional[Any]						=			1
               for j in range(self.c_max_length // (next_ncol * 2)):
                    for i in range(_UpperCAmelCase):
                         new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j])
                    current_root *= root
               # Second half of next step
               __A		:					List[str]						=			1
               for j in range(self.c_max_length // (next_ncol * 2)):
                    for i in range(_UpperCAmelCase):
                         new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j])
                    current_root *= root
               # Update
               __A		:					Optional[int]						=			new_dft
               __A		:					Tuple						=			next_ncol // 2
          return dft[0]


     def 				SCREAMING_SNAKE_CASE    (		self):

          '''simple docstring'''






          __A		:					int						=			self.__dft('A')
          __A		:					Optional[Any]						=			self.__dft('B')
          __A		:					str						=			[[dft_a[i] * dft_b[i] for i in range(self.c_max_length)]]
          del dft_a
          del dft_b

          # Corner Case
          if len(inverce_c[0]) <= 1:
               return inverce_c[0]
          # Inverse DFT
          __A		:					Dict						=			2
          while next_ncol <= self.c_max_length:
               __A		:					Optional[int]						=			[[] for i in range(_UpperCAmelCase)]
               __A		:					Any						=			self.root ** (next_ncol // 2)
               __A		:					Tuple						=			1
               # First half of next step
               for j in range(self.c_max_length // next_ncol):
                    for i in range(next_ncol // 2):
                         # Even positions
                         new_inverse_c[i].append(
                             (
                                 inverce_c[i][j]
                                 + inverce_c[i][j + self.c_max_length // next_ncol]
                             )
                             / 2)
                         # Odd positions
                         new_inverse_c[i + next_ncol // 2].append(
                             (
                                 inverce_c[i][j]
                                 - inverce_c[i][j + self.c_max_length // next_ncol]
                             )
                             / (2 * current_root))
                    current_root *= root
               # Update
               __A		:					int						=			new_inverse_c
               next_ncol *= 2
          # Unpack
          __A		:					Optional[int]						=			[round(x[0].real		,      8) + round(x[0].imag		,      8) * 1j for x in inverce_c]

          # Remove leading 0's
          while inverce_c[-1] == 0:
               inverce_c.pop()
          return inverce_c


     def __str__(		self):

          '''simple docstring'''






          __A		:					int						=			'A = ' + ' + '.join(
              F'{coef}*x^{i}' for coef, i in enumerate(self.polyA[: self.len_A]))
          __A		:					Optional[Any]						=			'B = ' + ' + '.join(
              F'{coef}*x^{i}' for coef, i in enumerate(self.polyB[: self.len_B]))
          __A		:					str						=			'A*B = ' + ' + '.join(
              F'{coef}*x^{i}' for coef, i in enumerate(self.product))

          return F'{a}\n{b}\n{c}'


# Unit tests
if __name__ == "__main__":
  import doctest

  doctest.testmod()