






'''simple docstring'''





from __future__ import annotations

import sys
def        UpperCAmelCase      (   _lowercase,      _lowercase      ):


    '''simple docstring'''



    if abs(UpperCamelCase__      ) == 1:
        return a, 0
    elif abs(UpperCamelCase__      ) == 1:
        return 0, b

    _lowercase     =	a, b
    _lowercase     =	1, 0
    _lowercase     =	0, 1

    while remainder != 0:
        _lowercase     =	old_remainder // remainder
        _lowercase     =	remainder, old_remainder - quotient * remainder
        _lowercase     =	coeff_a, old_coeff_a - quotient * coeff_a
        _lowercase     =	coeff_b, old_coeff_b - quotient * coeff_b

    # sign correction for negative numbers
    if a < 0:
        _lowercase     =	-old_coeff_a
    if b < 0:
        _lowercase     =	-old_coeff_b

    return old_coeff_a, old_coeff_b
def        UpperCAmelCase      (   ):


    '''simple docstring'''



    if len(sys.argv      ) < 3:
        print('2 integer arguments required'      )
        return 1
    _lowercase     =	int(sys.argv[1]      )
    _lowercase     =	int(sys.argv[2]      )
    print(extended_euclidean_algorithm(UpperCamelCase__,      UpperCamelCase__      )      )
    return 0


if __name__ == "__main__":
   raise SystemExit(main())








from __future__ import annotations
def        UpperCAmelCase      (   _lowercase,      _lowercase      ):


    '''simple docstring'''



    _lowercase     =	[None] * (len(_lowercase      ) + len(_lowercase      ))

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

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

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

    return sorted_array
def        UpperCAmelCase      (   _lowercase      ):


    '''simple docstring'''



    if len(_lowercase      ) <= 1:
        return array
    # the actual formula to calculate the middle element = left + (right - left) // 2
    # this avoids integer overflow in case of large N
    _lowercase     =	0 + (len(_lowercase      ) - 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
    _lowercase     =	array[:middle]
    _lowercase     =	array[middle:]

    return merge(merge_sort(_lowercase      ),      merge_sort(_lowercase      )      )


if __name__ == "__main__":
   import doctest

   doctest.testmod()
