


"""simple docstring"""





import unittest

import numpy as np

from transformers.testing_utils import require_pytesseract, require_torch
from transformers.utils import is_pytesseract_available, is_torch_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin, prepare_image_inputs


if is_torch_available():
 import torch

if is_pytesseract_available():
 from PIL import Image

 from transformers import LayoutLMvaImageProcessor



class 						snake_case_(				unittest.TestCase	):






     def __init__(		self     :    int    , UpperCamelCase_     :    Optional[Any]    , UpperCamelCase_     :    Tuple=7    , UpperCamelCase_     :    int=3    , UpperCamelCase_     :    Dict=1_8    , UpperCamelCase_     :    List[Any]=3_0    , UpperCamelCase_     :    str=4_0_0    , UpperCamelCase_     :    Any=True    , UpperCamelCase_     :    List[str]=None    , UpperCamelCase_     :    List[Any]=True    , ):
           lowerCAmelCase    :		Dict				=      size if size is not None else {'''height''': 1_8, '''width''': 1_8}
           lowerCAmelCase    :		str				=      parent
           lowerCAmelCase    :		int				=      batch_size
           lowerCAmelCase    :		List[str]				=      num_channels
           lowerCAmelCase    :		int				=      image_size
           lowerCAmelCase    :		Optional[int]				=      min_resolution
           lowerCAmelCase    :		List[Any]				=      max_resolution
           lowerCAmelCase    :		Dict				=      do_resize
           lowerCAmelCase    :		List[str]				=      size
           lowerCAmelCase    :		int				=      apply_ocr






     def    lowerCamelCase__   (		self     :    List[str] ):
           return {"do_resize": self.do_resize, "size": self.size, "apply_ocr": self.apply_ocr}



@require_torch
@require_pytesseract
class 						snake_case_(				a__							,    unittest.TestCase	):
     __UpperCamelCase     =    LayoutLMvaImageProcessor if is_pytesseract_available() else None






     def    lowerCamelCase__   (		self     :    Dict ):
           lowerCAmelCase    :		int				=      LayoutLMvaImageProcessingTester(self )






     @property
     def    lowerCamelCase__   (		self     :    int ):
           return self.image_processor_tester.prepare_image_processor_dict()






     def    lowerCamelCase__   (		self     :    Optional[int] ):
           lowerCAmelCase    :		List[Any]				=      self.image_processing_class(**self.image_processor_dict )
           self.assertTrue(hasattr(UpperCamelCase_    , '''do_resize''' ) )
           self.assertTrue(hasattr(UpperCamelCase_    , '''size''' ) )
           self.assertTrue(hasattr(UpperCamelCase_    , '''apply_ocr''' ) )






     def    lowerCamelCase__   (		self     :    Optional[Any] ):
           lowerCAmelCase    :		Tuple				=      self.image_processing_class.from_dict(self.image_processor_dict )
           self.assertEqual(image_processor.size    , {'''height''': 1_8, '''width''': 1_8} )

           lowerCAmelCase    :		Optional[Any]				=      self.image_processing_class.from_dict(self.image_processor_dict    , size=4_2 )
           self.assertEqual(image_processor.size    , {'''height''': 4_2, '''width''': 4_2} )






     def    lowerCamelCase__   (		self     :    int ):
           pass






     def    lowerCamelCase__   (		self     :    int ):
           # Initialize image_processing
           lowerCAmelCase    :		Tuple				=      self.image_processing_class(**self.image_processor_dict )
           # create random PIL images
           lowerCAmelCase    :		Any				=      prepare_image_inputs(self.image_processor_tester    , equal_resolution=UpperCamelCase_ )
           for image in image_inputs:
                 self.assertIsInstance(UpperCamelCase_    , Image.Image )

           # Test not batched input
           lowerCAmelCase    :		Optional[int]				=      image_processing(image_inputs[0]    , return_tensors='''pt''' )
           self.assertEqual(
               encoding.pixel_values.shape    , (
                   1,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )

           self.assertIsInstance(encoding.words    , UpperCamelCase_ )
           self.assertIsInstance(encoding.boxes    , UpperCamelCase_ )

           # Test batched
           lowerCAmelCase    :		Tuple				=      image_processing(UpperCamelCase_    , return_tensors='''pt''' ).pixel_values
           self.assertEqual(
               encoded_images.shape    , (
                   self.image_processor_tester.batch_size,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )






     def    lowerCamelCase__   (		self     :    Union[str, Any] ):
           # Initialize image_processing
           lowerCAmelCase    :		Any				=      self.image_processing_class(**self.image_processor_dict )
           # create random numpy tensors
           lowerCAmelCase    :		str				=      prepare_image_inputs(self.image_processor_tester    , equal_resolution=UpperCamelCase_    , numpify=UpperCamelCase_ )
           for image in image_inputs:
                 self.assertIsInstance(UpperCamelCase_    , np.ndarray )

           # Test not batched input
           lowerCAmelCase    :		List[Any]				=      image_processing(image_inputs[0]    , return_tensors='''pt''' ).pixel_values
           self.assertEqual(
               encoded_images.shape    , (
                   1,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )

           # Test batched
           lowerCAmelCase    :		Any				=      image_processing(UpperCamelCase_    , return_tensors='''pt''' ).pixel_values
           self.assertEqual(
               encoded_images.shape    , (
                   self.image_processor_tester.batch_size,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )






     def    lowerCamelCase__   (		self     :    Union[str, Any] ):
           # Initialize image_processing
           lowerCAmelCase    :		Optional[int]				=      self.image_processing_class(**self.image_processor_dict )
           # create random PyTorch tensors
           lowerCAmelCase    :		List[str]				=      prepare_image_inputs(self.image_processor_tester    , equal_resolution=UpperCamelCase_    , torchify=UpperCamelCase_ )
           for image in image_inputs:
                 self.assertIsInstance(UpperCamelCase_    , torch.Tensor )

           # Test not batched input
           lowerCAmelCase    :		Tuple				=      image_processing(image_inputs[0]    , return_tensors='''pt''' ).pixel_values
           self.assertEqual(
               encoded_images.shape    , (
                   1,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )

           # Test batched
           lowerCAmelCase    :		Any				=      image_processing(UpperCamelCase_    , return_tensors='''pt''' ).pixel_values
           self.assertEqual(
               encoded_images.shape    , (
                   self.image_processor_tester.batch_size,
                   self.image_processor_tester.num_channels,
                   self.image_processor_tester.size['''height'''],
                   self.image_processor_tester.size['''width'''],
               )    , )






     def    lowerCamelCase__   (		self     :    int ):
           # with apply_OCR = True
           lowerCAmelCase    :		Union[str, Any]				=      LayoutLMvaImageProcessor()

           from datasets import load_dataset

           lowerCAmelCase    :		List[Any]				=      load_dataset('''hf-internal-testing/fixtures_docvqa'''    , split='''test''' )

           lowerCAmelCase    :		Optional[int]				=      Image.open(ds[0]['''file'''] ).convert('''RGB''' )

           lowerCAmelCase    :		List[Any]				=      image_processing(UpperCamelCase_    , return_tensors='''pt''' )

           self.assertEqual(encoding.pixel_values.shape    , (1, 3, 2_2_4, 2_2_4) )
           self.assertEqual(len(encoding.words )    , len(encoding.boxes ) )

           # fmt: off
           # the words and boxes were obtained with Tesseract 4.1.1
           lowerCAmelCase    :		Optional[Any]				=      [['''11:14''', '''to''', '''11:39''', '''a.m''', '''11:39''', '''to''', '''11:44''', '''a.m.''', '''11:44''', '''a.m.''', '''to''', '''12:25''', '''p.m.''', '''12:25''', '''to''', '''12:58''', '''p.m.''', '''12:58''', '''to''', '''4:00''', '''p.m.''', '''2:00''', '''to''', '''5:00''', '''p.m.''', '''Coffee''', '''Break''', '''Coffee''', '''will''', '''be''', '''served''', '''for''', '''men''', '''and''', '''women''', '''in''', '''the''', '''lobby''', '''adjacent''', '''to''', '''exhibit''', '''area.''', '''Please''', '''move''', '''into''', '''exhibit''', '''area.''', '''(Exhibits''', '''Open)''', '''TRRF''', '''GENERAL''', '''SESSION''', '''(PART''', '''|)''', '''Presiding:''', '''Lee''', '''A.''', '''Waller''', '''TRRF''', '''Vice''', '''President''', '''“Introductory''', '''Remarks”''', '''Lee''', '''A.''', '''Waller,''', '''TRRF''', '''Vice''', '''Presi-''', '''dent''', '''Individual''', '''Interviews''', '''with''', '''TRRF''', '''Public''', '''Board''', '''Members''', '''and''', '''Sci-''', '''entific''', '''Advisory''', '''Council''', '''Mem-''', '''bers''', '''Conducted''', '''by''', '''TRRF''', '''Treasurer''', '''Philip''', '''G.''', '''Kuehn''', '''to''', '''get''', '''answers''', '''which''', '''the''', '''public''', '''refrigerated''', '''warehousing''', '''industry''', '''is''', '''looking''', '''for.''', '''Plus''', '''questions''', '''from''', '''the''', '''floor.''', '''Dr.''', '''Emil''', '''M.''', '''Mrak,''', '''University''', '''of''', '''Cal-''', '''ifornia,''', '''Chairman,''', '''TRRF''', '''Board;''', '''Sam''', '''R.''', '''Cecil,''', '''University''', '''of''', '''Georgia''', '''College''', '''of''', '''Agriculture;''', '''Dr.''', '''Stanley''', '''Charm,''', '''Tufts''', '''University''', '''School''', '''of''', '''Medicine;''', '''Dr.''', '''Robert''', '''H.''', '''Cotton,''', '''ITT''', '''Continental''', '''Baking''', '''Company;''', '''Dr.''', '''Owen''', '''Fennema,''', '''University''', '''of''', '''Wis-''', '''consin;''', '''Dr.''', '''Robert''', '''E.''', '''Hardenburg,''', '''USDA.''', '''Questions''', '''and''', '''Answers''', '''Exhibits''', '''Open''', '''Capt.''', '''Jack''', '''Stoney''', '''Room''', '''TRRF''', '''Scientific''', '''Advisory''', '''Council''', '''Meeting''', '''Ballroom''', '''Foyer''']]  # noqa: E231
           lowerCAmelCase    :		List[Any]				=      [[[1_4_1, 5_7, 2_1_4, 6_9], [2_2_8, 5_8, 2_5_2, 6_9], [1_4_1, 7_5, 2_1_6, 8_8], [2_3_0, 7_9, 2_8_0, 8_8], [1_4_2, 2_6_0, 2_1_8, 2_7_3], [2_3_0, 2_6_1, 2_5_5, 2_7_3], [1_4_3, 2_7_9, 2_1_8, 2_9_0], [2_3_1, 2_8_2, 2_9_0, 2_9_1], [1_4_3, 3_4_2, 2_1_8, 3_5_4], [2_3_1, 3_4_5, 2_8_9, 3_5_5], [2_0_2, 3_6_2, 2_2_7, 3_7_3], [1_4_3, 3_7_9, 2_2_0, 3_9_2], [2_3_1, 3_8_2, 2_9_1, 3_9_4], [1_4_4, 7_1_4, 2_2_0, 7_2_6], [2_3_1, 7_1_5, 2_5_6, 7_2_6], [1_4_4, 7_3_2, 2_2_0, 7_4_5], [2_3_2, 7_3_6, 2_9_1, 7_4_7], [1_4_4, 7_6_9, 2_1_8, 7_8_2], [2_3_1, 7_7_0, 2_5_6, 7_8_2], [1_4_1, 7_8_8, 2_0_2, 8_0_1], [2_1_5, 7_9_1, 2_7_4, 8_0_4], [1_4_3, 8_2_6, 2_0_4, 8_3_8], [2_1_5, 8_2_6, 2_4_0, 8_3_8], [1_4_2, 8_4_4, 2_0_2, 8_5_7], [2_1_5, 8_4_7, 2_7_4, 8_5_9], [3_3_4, 5_7, 4_2_7, 6_9], [4_4_0, 5_7, 5_2_2, 6_9], [3_6_9, 7_5, 4_6_1, 8_8], [4_6_9, 7_5, 5_1_6, 8_8], [5_2_8, 7_6, 5_6_2, 8_8], [5_7_0, 7_6, 6_6_7, 8_8], [6_7_5, 7_5, 7_1_1, 8_7], [7_2_1, 7_9, 7_7_8, 8_8], [7_8_9, 7_5, 8_4_0, 8_8], [3_6_9, 9_7, 4_7_0, 1_0_7], [4_8_4, 9_4, 5_0_7, 1_0_6], [5_1_8, 9_4, 5_6_2, 1_0_7], [5_7_6, 9_4, 6_5_5, 1_1_0], [6_6_8, 9_4, 7_9_2, 1_0_9], [8_0_4, 9_5, 8_2_9, 1_0_7], [3_6_9, 1_1_3, 4_6_5, 1_2_5], [4_7_7, 1_1_6, 5_4_7, 1_2_5], [5_6_2, 1_1_3, 6_5_8, 1_2_5], [6_7_1, 1_1_6, 7_4_8, 1_2_5], [7_6_1, 1_1_3, 8_1_1, 1_2_5], [3_6_9, 1_3_1, 4_6_5, 1_4_3], [4_7_7, 1_3_3, 5_4_8, 1_4_3], [5_6_3, 1_3_0, 6_9_8, 1_4_5], [7_1_0, 1_3_0, 8_0_2, 1_4_6], [3_3_6, 1_7_1, 4_1_2, 1_8_3], [4_2_3, 1_7_1, 5_7_2, 1_8_3], [5_8_2, 1_7_0, 7_1_6, 1_8_4], [7_2_8, 1_7_1, 8_1_7, 1_8_7], [8_2_9, 1_7_1, 8_4_4, 1_8_6], [3_3_8, 1_9_7, 4_8_2, 2_1_2], [5_0_7, 1_9_6, 5_5_7, 2_0_9], [5_6_9, 1_9_6, 5_9_5, 2_0_8], [6_1_0, 1_9_6, 7_0_2, 2_0_9], [5_0_5, 2_1_4, 5_8_3, 2_2_6], [5_9_5, 2_1_4, 6_5_6, 2_2_7], [6_7_0, 2_1_5, 8_0_7, 2_2_7], [3_3_5, 2_5_9, 5_4_3, 2_7_4], [5_5_6, 2_5_9, 7_0_8, 2_7_2], [3_7_2, 2_7_9, 4_2_2, 2_9_1], [4_3_5, 2_7_9, 4_6_0, 2_9_1], [4_7_4, 2_7_9, 5_7_4, 2_9_2], [5_8_7, 2_7_8, 6_6_4, 2_9_1], [6_7_6, 2_7_8, 7_3_8, 2_9_1], [7_5_1, 2_7_9, 8_3_4, 2_9_1], [3_7_2, 2_9_8, 4_3_4, 3_1_0], [3_3_5, 3_4_1, 4_8_3, 3_5_4], [4_9_7, 3_4_1, 6_5_5, 3_5_4], [6_6_7, 3_4_1, 7_2_8, 3_5_4], [7_4_0, 3_4_1, 8_2_5, 3_5_4], [3_3_5, 3_6_0, 4_3_0, 3_7_2], [4_4_2, 3_6_0, 5_3_4, 3_7_2], [5_4_5, 3_5_9, 6_8_7, 3_7_2], [6_9_7, 3_6_0, 7_5_4, 3_7_2], [7_6_5, 3_6_0, 8_2_3, 3_7_3], [3_3_4, 3_7_8, 4_2_8, 3_9_1], [4_4_0, 3_7_8, 5_7_7, 3_9_4], [5_9_0, 3_7_8, 7_0_5, 3_9_1], [7_2_0, 3_7_8, 8_0_1, 3_9_1], [3_3_4, 3_9_7, 4_0_0, 4_0_9], [3_7_0, 4_1_6, 5_2_9, 4_2_9], [5_4_4, 4_1_6, 5_7_6, 4_3_2], [5_8_7, 4_1_6, 6_6_5, 4_2_8], [6_7_7, 4_1_6, 8_1_4, 4_2_9], [3_7_2, 4_3_5, 4_5_2, 4_5_0], [4_6_5, 4_3_4, 4_9_5, 4_4_7], [5_1_1, 4_3_4, 6_0_0, 4_4_7], [6_1_1, 4_3_6, 6_3_7, 4_4_7], [6_4_9, 4_3_6, 6_9_4, 4_5_1], [7_0_5, 4_3_8, 8_2_4, 4_4_7], [3_6_9, 4_5_3, 4_5_2, 4_6_6], [4_6_4, 4_5_4, 5_0_9, 4_6_6], [5_2_2, 4_5_3, 6_1_1, 4_6_9], [6_2_5, 4_5_3, 7_9_2, 4_6_9], [3_7_0, 4_7_2, 5_5_6, 4_8_8], [5_7_0, 4_7_2, 6_8_4, 4_8_7], [6_9_7, 4_7_2, 7_1_8, 4_8_5], [7_3_2, 4_7_2, 8_3_5, 4_8_8], [3_6_9, 4_9_0, 4_1_1, 5_0_3], [4_2_5, 4_9_0, 4_8_4, 5_0_3], [4_9_6, 4_9_0, 6_3_5, 5_0_6], [6_4_5, 4_9_0, 7_0_7, 5_0_3], [7_1_8, 4_9_1, 7_6_1, 5_0_3], [7_7_1, 4_9_0, 8_4_0, 5_0_3], [3_3_6, 5_1_0, 3_7_4, 5_2_1], [3_8_8, 5_1_0, 4_4_7, 5_2_2], [4_6_0, 5_1_0, 4_8_9, 5_2_1], [5_0_3, 5_1_0, 5_8_0, 5_2_2], [5_9_2, 5_0_9, 7_3_6, 5_2_5], [7_4_5, 5_0_9, 7_7_0, 5_2_2], [7_8_1, 5_0_9, 8_4_0, 5_2_2], [3_3_8, 5_2_8, 4_3_4, 5_4_1], [4_4_8, 5_2_8, 5_9_6, 5_4_1], [6_0_9, 5_2_7, 6_8_7, 5_4_0], [7_0_0, 5_2_8, 7_9_2, 5_4_1], [3_3_6, 5_4_6, 3_9_7, 5_5_9], [4_0_7, 5_4_6, 4_3_1, 5_5_9], [4_4_3, 5_4_6, 5_2_5, 5_6_0], [5_3_7, 5_4_6, 6_8_0, 5_6_2], [6_8_8, 5_4_6, 7_1_4, 5_5_9], [7_2_2, 5_4_6, 8_3_7, 5_6_2], [3_3_6, 5_6_5, 4_4_9, 5_8_1], [4_6_1, 5_6_5, 4_8_5, 5_7_7], [4_9_7, 5_6_5, 6_6_5, 5_8_1], [6_8_1, 5_6_5, 7_1_8, 5_7_7], [7_3_2, 5_6_5, 8_3_7, 5_8_0], [3_3_7, 5_8_4, 4_3_8, 5_9_7], [4_5_2, 5_8_3, 5_2_1, 5_9_6], [5_3_5, 5_8_4, 6_7_7, 5_9_9], [6_9_0, 5_8_3, 7_8_7, 5_9_6], [8_0_1, 5_8_3, 8_2_5, 5_9_6], [3_3_8, 6_0_2, 4_7_8, 6_1_5], [4_9_2, 6_0_2, 5_3_0, 6_1_4], [5_4_3, 6_0_2, 6_3_8, 6_1_5], [6_5_0, 6_0_2, 6_7_6, 6_1_4], [6_8_8, 6_0_2, 7_8_8, 6_1_5], [8_0_2, 6_0_2, 8_4_3, 6_1_4], [3_3_7, 6_2_1, 5_0_2, 6_3_3], [5_1_6, 6_2_1, 6_1_5, 6_3_7], [6_2_9, 6_2_1, 7_7_4, 6_3_6], [7_8_9, 6_2_1, 8_2_7, 6_3_3], [3_3_7, 6_3_9, 4_1_8, 6_5_2], [4_3_2, 6_4_0, 5_7_1, 6_5_3], [5_8_7, 6_3_9, 7_3_1, 6_5_5], [7_4_3, 6_3_9, 7_6_9, 6_5_2], [7_8_0, 6_3_9, 8_4_1, 6_5_2], [3_3_8, 6_5_8, 4_4_0, 6_7_3], [4_5_5, 6_5_8, 4_9_1, 6_7_0], [5_0_8, 6_5_8, 6_0_2, 6_7_1], [6_1_6, 6_5_8, 6_3_8, 6_7_0], [6_5_4, 6_5_8, 8_3_5, 6_7_4], [3_3_7, 6_7_7, 4_2_9, 6_8_9], [3_3_7, 7_1_4, 4_8_2, 7_2_6], [4_9_5, 7_1_4, 5_4_8, 7_2_6], [5_6_1, 7_1_4, 6_8_3, 7_2_6], [3_3_8, 7_7_0, 4_6_1, 7_8_2], [4_7_4, 7_6_9, 5_5_4, 7_8_5], [4_8_9, 7_8_8, 5_6_2, 8_0_3], [5_7_6, 7_8_8, 6_4_3, 8_0_1], [6_5_6, 7_8_7, 7_5_1, 8_0_4], [7_6_4, 7_8_8, 8_4_4, 8_0_1], [3_3_4, 8_2_5, 4_2_1, 8_3_8], [4_3_0, 8_2_4, 5_7_4, 8_3_8], [5_8_4, 8_2_4, 7_2_3, 8_4_1], [3_3_5, 8_4_4, 4_5_0, 8_5_7], [4_6_4, 8_4_3, 5_8_3, 8_6_0], [6_2_8, 8_6_2, 7_5_5, 8_7_5], [7_6_9, 8_6_1, 8_4_8, 8_7_8]]]  # noqa: E231
           # fmt: on

           self.assertListEqual(encoding.words    , UpperCamelCase_ )
           self.assertListEqual(encoding.boxes    , UpperCamelCase_ )

           # with apply_OCR = False
           lowerCAmelCase    :		Union[str, Any]				=      LayoutLMvaImageProcessor(apply_ocr=UpperCamelCase_ )

           lowerCAmelCase    :		Union[str, Any]				=      image_processing(UpperCamelCase_    , return_tensors='''pt''' )

           self.assertEqual(encoding.pixel_values.shape    , (1, 3, 2_2_4, 2_2_4) )






"""simple docstring"""





import mpmath  # for roots of unity
import numpy as np



class 						snake_case_:






     def __init__(		self     :    str    , UpperCamelCase_     :    int=None    , UpperCamelCase_     :    List[str]=None ):
           # Input as list
           lowerCAmelCase    :		str				=      list(poly_a or [0] )[:]
           lowerCAmelCase    :		Any				=      list(poly_b or [0] )[:]

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

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

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

           # The product
           lowerCAmelCase    :		int				=      self.__multiply()






     def    lowerCamelCase__   (		self     :    List[str]    , UpperCamelCase_     :    str ):
           lowerCAmelCase    :		Optional[Any]				=      [[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]
           #
           lowerCAmelCase    :		Tuple				=      self.c_max_length // 2
           while next_ncol > 0:
                 lowerCAmelCase    :		Dict				=      [[] for i in range(UpperCamelCase_ )]
                 lowerCAmelCase    :		List[Any]				=      self.root**next_ncol

                 # First half of next step
                 lowerCAmelCase    :		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
                 lowerCAmelCase    :		int				=      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
                 lowerCAmelCase    :		Optional[Any]				=      new_dft
                 lowerCAmelCase    :		Union[str, Any]				=      next_ncol // 2
           return dft[0]






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


