



import mpmath  # for roots of unity
import numpy as np



class 	lowerCamelCase__      :




		'''simple docstring'''



		def __init__(self		,__lowerCamelCase=None		,__lowerCamelCase=None			)					->      Optional[int]:

						"""simple docstring"""






						lowerCAmelCase__					:    Optional[Any]												=					list(poly_a or [0]			)[:]
						lowerCAmelCase__					:    Tuple												=					list(poly_b or [0]			)[:]

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

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

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

						# The product
						lowerCAmelCase__					:    Any												=					self.__multiply()



		def 		lowerCAmelCase__				(self		,__lowerCamelCase			)					->      Dict:

						"""simple docstring"""






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

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



		def 		lowerCAmelCase__				(self			)					->      str:

						"""simple docstring"""






						lowerCAmelCase__					:    Union[str, Any]												=					self.__dft('''A'''			)
						lowerCAmelCase__					:    Optional[int]												=					self.__dft('''B'''			)
						lowerCAmelCase__					:    Optional[int]												=					[[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
						lowerCAmelCase__					:    Optional[int]												=					2
						while next_ncol <= self.c_max_length:
										lowerCAmelCase__					:    Optional[Any]												=					[[] for i in range(__lowerCamelCase			)]
										lowerCAmelCase__					:    Optional[Any]												=					self.root ** (next_ncol // 2)
										lowerCAmelCase__					:    Union[str, 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
										lowerCAmelCase__					:    Optional[int]												=					new_inverse_c
										next_ncol *= 2
						# Unpack
						lowerCAmelCase__					:    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			)					->      List[str]:

						"""simple docstring"""






						lowerCAmelCase__					:    List[str]												=					'''A = ''' + ''' + '''.join(
						    f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]			)			)
						lowerCAmelCase__					:    Any												=					'''B = ''' + ''' + '''.join(
						    f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]			)			)
						lowerCAmelCase__					:    Tuple												=					'''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()






def      lowerCAmelCase__		(   lowerCamelCase_		:		str = "The quick brown fox jumps over the lazy dog"	,):





				'''simple docstring'''

				lowerCAmelCase__					:    Any												=					set()

				# Replace all the whitespace in our sentence
				lowerCAmelCase__					:    List[Any]												=					input_str.replace(''' '''	,'''''')
				for alpha in input_str:
								if "a" <= alpha.lower() <= "z":
												frequency.add(alpha.lower())
				return len(lowerCamelCase_) == 26






def      lowerCAmelCase__		(   lowerCamelCase_		:		str = "The quick brown fox jumps over the lazy dog"	,):





				'''simple docstring'''

				lowerCAmelCase__					:    List[str]												=					[False] * 26
				for char in input_str:
								if char.islower():
												lowerCAmelCase__					:    Union[str, Any]												=					True
								elif char.isupper():
												lowerCAmelCase__					:    str												=					True
				return all(lowerCamelCase_)






def      lowerCAmelCase__		(   lowerCamelCase_		:		str = "The quick brown fox jumps over the lazy dog"	,):





				'''simple docstring'''

				return len({char for char in input_str.lower() if char.isalpha()}) == 26






def      lowerCAmelCase__		(   ):





				'''simple docstring'''

				from timeit import timeit

				lowerCAmelCase__					:    Optional[Any]												=					'''from __main__ import is_pangram, is_pangram_faster, is_pangram_fastest'''
				print(timeit('''is_pangram()'''	,setup=lowerCamelCase_))
				print(timeit('''is_pangram_faster()'''	,setup=lowerCamelCase_))
				print(timeit('''is_pangram_fastest()'''	,setup=lowerCamelCase_))
				# 5.348480500048026, 2.6477354579837993, 1.8470395830227062
				# 5.036091582966037, 2.644472333951853,  1.8869528750656173


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							benchmark()

