






import mpmath  # for roots of unity
import numpy as np


class 							__a							:





		'''simple docstring'''



		def __init__(						self ,    UpperCamelCase__=None ,    UpperCamelCase__=None       ):
						# Input as list
						SCREAMING_SNAKE_CASE_   :	int													=   list(poly_a or [0]       )[:]
						SCREAMING_SNAKE_CASE_   :	Optional[Any]													=   list(poly_b or [0]       )[:]

						# Remove leading zero coefficients
						while self.polyA[-1] == 0:
										self.polyA.pop()
						SCREAMING_SNAKE_CASE_   :	List[Any]													=   len(self.polyA       )

						while self.polyB[-1] == 0:
										self.polyB.pop()
						SCREAMING_SNAKE_CASE_   :	Union[str, Any]													=   len(self.polyB       )

						# Add 0 to make lengths equal a power of 2
						SCREAMING_SNAKE_CASE_   :	str													=   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
						SCREAMING_SNAKE_CASE_   :	Dict													=   complex(mpmath.root(x=1 ,    n=self.c_max_length ,    k=1       )       )

						# The product
						SCREAMING_SNAKE_CASE_   :	Optional[Any]													=   self.__multiply()


		def   __snake_case			(						self ,    UpperCamelCase__       ):
						SCREAMING_SNAKE_CASE_   :	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]
						#
						SCREAMING_SNAKE_CASE_   :	Optional[Any]													=   self.c_max_length // 2
						while next_ncol > 0:
										SCREAMING_SNAKE_CASE_   :	Any													=   [[] for i in range(UpperCamelCase__       )]
										SCREAMING_SNAKE_CASE_   :	Tuple													=   self.root**next_ncol

										# First half of next step
										SCREAMING_SNAKE_CASE_   :	Dict													=   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
										SCREAMING_SNAKE_CASE_   :	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
										# Update
										SCREAMING_SNAKE_CASE_   :	str													=   new_dft
										SCREAMING_SNAKE_CASE_   :	int													=   next_ncol // 2
						return dft[0]


		def   __snake_case			(						self       ):
						SCREAMING_SNAKE_CASE_   :	str													=   self.__dft('A'       )
						SCREAMING_SNAKE_CASE_   :	List[Any]													=   self.__dft('B'       )
						SCREAMING_SNAKE_CASE_   :	Dict													=   [[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
						SCREAMING_SNAKE_CASE_   :	List[Any]													=   2
						while next_ncol <= self.c_max_length:
										SCREAMING_SNAKE_CASE_   :	List[str]													=   [[] for i in range(UpperCamelCase__       )]
										SCREAMING_SNAKE_CASE_   :	Tuple													=   self.root ** (next_ncol // 2)
										SCREAMING_SNAKE_CASE_   :	List[Any]													=   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
										SCREAMING_SNAKE_CASE_   :	int													=   new_inverse_c
										next_ncol *= 2
						# Unpack
						SCREAMING_SNAKE_CASE_   :	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       ):
						SCREAMING_SNAKE_CASE_   :	Any													=   'A = ' + ' + '.join(
						    F'''{coef}*x^{i}''' for coef, i in enumerate(self.polyA[: self.len_A]       )       )
						SCREAMING_SNAKE_CASE_   :	Union[str, Any]													=   'B = ' + ' + '.join(
						    F'''{coef}*x^{i}''' for coef, i in enumerate(self.polyB[: self.len_B]       )       )
						SCREAMING_SNAKE_CASE_   :	Union[str, Any]													=   '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()







import copy
from dataclasses import dataclass
from pathlib import Path
from typing import Dict, Optional, Union


@dataclass
class 							__a							:





		'''simple docstring'''



		UpperCAmelCase__      :				Optional[Union[str, Path]]				    =						None
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				Optional[Dict]				    =						None
		UpperCAmelCase__      :				Optional[str]				    =						None
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				bool				    =						True
		UpperCAmelCase__      :				Optional[int]				    =						None
		UpperCAmelCase__      :				int				    =						1
		UpperCAmelCase__      :				Optional[Union[str, bool]]				    =						None
		UpperCAmelCase__      :				bool				    =						False
		UpperCAmelCase__      :				Optional[Dict]				    =						None
		UpperCAmelCase__      :				Optional[str]				    =						None


		def   __snake_case			(						self       ):
						return self.__class__(**{k: copy.deepcopy(UpperCamelCase__       ) for k, v in self.__dict__.items()}       )