from typing import Tuple


def ext_gcd(a: int, b: int) -> Tuple[int, int, int]:
    """Extended Euclidean algorithm

    solve ax + by = gcd(a, b)

    Parameters
    ----------
    a
    b

    Returns
    -------
        (d, x, y) s.t. ax + by = gcd(a, b)
    """

    if b == 0:
        return a, 1, 0
    d, y, x = ext_gcd(b, a % b)
    return d, x, y - (a // b) * x