






'''simple docstring'''



import mpmath  # for roots of unity
import numpy as np
class 				__SCREAMING_SNAKE_CASE							:




      def __init__(	self			, lowerCamelCase=None			, lowerCamelCase=None   )				->List[str]:



         '''simple docstring'''
         # Input as list
         __a					  =     list(poly_a or [0]   )[:]
         __a					  =     list(poly_b or [0]   )[:]

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

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

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

         # The product
         __a					  =     self.__multiply()




      def 			__UpperCamelCase				(	self			, lowerCamelCase   )				->Any:



         '''simple docstring'''
         __a					  =     [[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]
         #
         __a					  =     self.c_max_length // 2
         while next_ncol > 0:
            __a					  =     [[] for i in range(lowerCamelCase   )]
            __a					  =     self.root**next_ncol

            # First half of next step
            __a					  =     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
            __a					  =     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
            __a					  =     new_dft
            __a					  =     next_ncol // 2
         return dft[0]




      def 			__UpperCamelCase				(	self   )				->int:



         '''simple docstring'''
         __a					  =     self.__dft('A'   )
         __a					  =     self.__dft('B'   )
         __a					  =     [[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					  =     2
         while next_ncol <= self.c_max_length:
            __a					  =     [[] for i in range(lowerCamelCase   )]
            __a					  =     self.root ** (next_ncol // 2)
            __a					  =     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					  =     new_inverse_c
            next_ncol *= 2
         # Unpack
         __a					  =     [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:



         '''simple docstring'''
         __a					  =     'A = ' + ' + '.join(
             F"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]   )   )
         __a					  =     'B = ' + ' + '.join(
             F"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]   )   )
         __a					  =     '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()







'''simple docstring'''



from multiprocessing import Lock, Pipe, Process

# lock used to ensure that two processes do not access a pipe at the same time
__UpperCamelCase   :							Optional[int]         =   Lock()



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						Tuple,       SCREAMING_SNAKE_CASE__:						Any,       SCREAMING_SNAKE_CASE__:						Tuple,       SCREAMING_SNAKE_CASE__:						str,       SCREAMING_SNAKE_CASE__:						Optional[Any],       SCREAMING_SNAKE_CASE__:						Any,       SCREAMING_SNAKE_CASE__:						List[Any]     )	->      int:

   """simple docstring"""
   global process_lock

   # we perform n swaps since after n swaps we know we are sorted
   # we *could* stop early if we are sorted already, but it takes as long to
   # find out we are sorted as it does to sort the list with this algorithm
   for i in range(0,       10     ):
      if (i + position) % 2 == 0 and r_send is not None:
         # send your value to your right neighbor
         process_lock.acquire()
         r_send[1].send(SCREAMING_SNAKE_CASE__     )
         process_lock.release()

         # receive your right neighbor's value
         process_lock.acquire()
         __a					  =     rr_cv[0].recv()
         process_lock.release()

         # take the lower value since you are on the left
         __a					  =     min(SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__     )
      elif (i + position) % 2 != 0 and l_send is not None:
         # send your value to your left neighbor
         process_lock.acquire()
         l_send[1].send(SCREAMING_SNAKE_CASE__     )
         process_lock.release()

         # receive your left neighbor's value
         process_lock.acquire()
         __a					  =     lr_cv[0].recv()
         process_lock.release()

         # take the higher value since you are on the right
         __a					  =     max(SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__     )
    # after all swaps are performed, send the values back to main
   result_pipe[1].send(SCREAMING_SNAKE_CASE__     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						Tuple     )	->      Optional[Any]:

   """simple docstring"""
   __a					  =     []
   __a					  =     []
   # initialize the list of pipes where the values will be retrieved
   for _ in arr:
      result_pipe.append(Pipe()     )
   # creates the processes
   # the first and last process only have one neighbor so they are made outside
   # of the loop
   __a					  =     Pipe()
   __a					  =     Pipe()
   process_array_.append(
       Process(
           target=SCREAMING_SNAKE_CASE__,       args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0]),       )     )
   __a					  =     temp_rs
   __a					  =     temp_rr

   for i in range(1,       len(SCREAMING_SNAKE_CASE__     ) - 1     ):
      __a					  =     Pipe()
      __a					  =     Pipe()
      process_array_.append(
          Process(
              target=SCREAMING_SNAKE_CASE__,       args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i]),       )     )
      __a					  =     temp_rs
      __a					  =     temp_rr

   process_array_.append(
       Process(
           target=SCREAMING_SNAKE_CASE__,       args=(
               len(SCREAMING_SNAKE_CASE__     ) - 1,
               arr[len(SCREAMING_SNAKE_CASE__     ) - 1],
               temp_ls,
               None,
               temp_lr,
               None,
               result_pipe[len(SCREAMING_SNAKE_CASE__     ) - 1],
           ),       )     )

   # start the processes
   for p in process_array_:
      p.start()

   # wait for the processes to end and write their values to the list
   for p in range(0,       len(SCREAMING_SNAKE_CASE__     )     ):
      __a					  =     result_pipe[p][0].recv()
      process_array_[p].join()
   return arr



def  __UpperCAmelCase						(					)	->      Any:

   """simple docstring"""
   __a					  =     list(range(10,       0,       -1     )     )
   print('Initial List'     )
   print(*SCREAMING_SNAKE_CASE__     )
   __a					  =     odd_even_transposition(SCREAMING_SNAKE_CASE__     )
   print('Sorted List\n'     )
   print(*SCREAMING_SNAKE_CASE__     )


if __name__ == "__main__":
 main()