import typing


def extgcd(a: int, b: int) -> typing.Tuple[int, int, int]:
    """
    Обобщённый алгоритм Евклида.

    Возвращает наибольший общий делитель и их коэффициенты Безу.
    Оба числа должны быть натуральными.

    Пример:

    egcd(12, 8) -> (4, 1, -1), при том 4 = 1 * 12 - 1 * 8
    """
    if a <= 0 or b <= 0:
        raise ValueError("Числа могут быть только натуральными")
    # if a < b:
    #     a, b = b, a  # Ломает алгоритм
    u1, u2, u3 = a, 1, 0
    v1, v2, v3 = b, 0, 1
    while v1:
        q = u1 // v1
        t1, t2, t3 = u1 % v1, u2 - q * v2, u3 - q * v3
        u1, u2, u3 = v1, v2, v3
        v1, v2, v3 = t1, t2, t3
    return u1, u2, u3