





def 				__UpperCamelCase  (		snake_case    ,	snake_case     )  ->						Optional[int]:


   '''simple docstring'''







   if len(str(snake_case     )     ) == 1 or len(str(snake_case     )     ) == 1:
      return a * b

   __A				 =       max(len(str(snake_case     )     )    ,	len(str(snake_case     )     )     )
   __A				 =       ma // 2

   __A ,						__A				 =       divmod(snake_case    ,	1_0**ma     )
   __A ,						__A				 =       divmod(snake_case    ,	1_0**ma     )

   __A				 =       karatsuba(snake_case    ,	snake_case     )
   __A				 =       karatsuba((aa + aa)    ,	(ba + ba)     )
   __A				 =       karatsuba(snake_case    ,	snake_case     )

   return (z * 1_0 ** (2 * ma)) + ((y - z - x) * 1_0 ** (ma)) + (x)
def 				__UpperCamelCase  (		)  ->						List[Any]:


   '''simple docstring'''







   print(karatsuba(1_5_4_6_3    ,	2_3_4_8_9     )     )


if __name__ == "__main__":
    main()








from __future__ import annotations
def 				__UpperCamelCase  (		snake_case    ,	snake_case     )  ->						list:


   '''simple docstring'''







   __A				 =       [None] * (len(snake_case     ) + len(snake_case     ))

   __A				 =       0  # pointer to current index for left Half
   __A				 =       0  # pointer to current index for the right Half
   __A				 =       0  # pointer to current index for the sorted array Half

   while pointera < len(snake_case     ) and pointera < len(snake_case     ):
      if left_half[pointera] < right_half[pointera]:
         __A				 =       left_half[pointera]
         pointera += 1
         index += 1
      else:
         __A				 =       right_half[pointera]
         pointera += 1
         index += 1
   while pointera < len(snake_case     ):
      __A				 =       left_half[pointera]
      pointera += 1
      index += 1

   while pointera < len(snake_case     ):
      __A				 =       right_half[pointera]
      pointera += 1
      index += 1

   return sorted_array
def 				__UpperCamelCase  (		snake_case     )  ->						list:


   '''simple docstring'''







   if len(snake_case     ) <= 1:
      return array
   # the actual formula to calculate the middle element = left + (right - left) // 2
   # this avoids integer overflow in case of large N
   __A				 =       0 + (len(snake_case     ) - 0) // 2

   # Split the array into halves till the array length becomes equal to One
   # merge the arrays of single length returned by mergeSort function and
   # pass them into the merge arrays function which merges the array
   __A				 =       array[:middle]
   __A				 =       array[middle:]

   return merge(merge_sort(snake_case     )    ,	merge_sort(snake_case     )     )


if __name__ == "__main__":
    import doctest

    doctest.testmod()

