'''simple docstring'''




def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					Union[str, Any]:
    if len(str(UpperCamelCase__       )       ) == 1 or len(str(UpperCamelCase__       )       ) == 1:
        return a * b

    __lowerCamelCase						=						max(len(str(UpperCamelCase__       )       )       ,						len(str(UpperCamelCase__       )       )       )
    __lowerCamelCase						=						ma // 2

    __lowerCamelCase			,						__lowerCamelCase						=						divmod(UpperCamelCase__       ,						10**ma       )
    __lowerCamelCase			,						__lowerCamelCase						=						divmod(UpperCamelCase__       ,						10**ma       )

    __lowerCamelCase						=						karatsuba(UpperCamelCase__       ,						UpperCamelCase__       )
    __lowerCamelCase						=						karatsuba((aa + aa)       ,						(ba + ba)       )
    __lowerCamelCase						=						karatsuba(UpperCamelCase__       ,						UpperCamelCase__       )

    return (z * 10 ** (2 * ma)) + ((y - z - x) * 10 ** (ma)) + (x)






def __lowerCAmelCase				(							)			->					Any:
    print(karatsuba(1_54_63       ,						2_34_89       )       )


if __name__ == "__main__":
  main()

'''simple docstring'''




from __future__ import annotations






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       )			->					tuple[float, float]:
    assert (
        c % greatest_common_divisor(UpperCamelCase__       ,						UpperCamelCase__       ) == 0
    )  # greatest_common_divisor(a,b) function implemented below
    ((__lowerCamelCase)			,						(__lowerCamelCase)			,						(__lowerCamelCase))						=						extended_gcd(UpperCamelCase__       ,						UpperCamelCase__       )  # extended_gcd(a,b) function implemented below
    __lowerCamelCase						=						c / d
    return (r * x, r * y)






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__ = 2       )			->					None:
    ((__lowerCamelCase)			,						(__lowerCamelCase))						=						diophantine(UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       )  # Initial value
    __lowerCamelCase						=						greatest_common_divisor(UpperCamelCase__       ,						UpperCamelCase__       )
    __lowerCamelCase						=						a // d
    __lowerCamelCase						=						b // d

    for i in range(UpperCamelCase__       ):
        __lowerCamelCase						=						xa + i * q
        __lowerCamelCase						=						ya - i * p
        print(UpperCamelCase__       ,						UpperCamelCase__       )






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					int:
    if a < b:
        __lowerCamelCase			,						__lowerCamelCase						=						b, a

    while a % b != 0:
        __lowerCamelCase			,						__lowerCamelCase						=						b, a % b

    return b






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					tuple[int, int, int]:
    assert a >= 0 and b >= 0

    if b == 0:
        __lowerCamelCase			,						__lowerCamelCase			,						__lowerCamelCase						=						a, 1, 0
    else:
        ((__lowerCamelCase)			,						(__lowerCamelCase)			,						(__lowerCamelCase))						=						extended_gcd(UpperCamelCase__       ,						a % b       )
        __lowerCamelCase						=						q
        __lowerCamelCase						=						p - q * (a // b)

    assert a % d == 0 and b % d == 0
    assert d == a * x + b * y

    return (d, x, y)


if __name__ == "__main__":
  from doctest import testmod

  testmod(name="diophantine", verbose=True)
  testmod(name="diophantine_all_soln", verbose=True)
  testmod(name="extended_gcd", verbose=True)
  testmod(name="greatest_common_divisor", verbose=True)
