def xgcd(a: int, b: int) -> tuple:
    """Extended Euclidean (GCD) algorithm

    gcd(a, b) = u*a + v*b

    Returns gdc, u, v
    """
    x, x1, y, y1 = 1, 0, 0, 1
    while b:
        q, a, b = a // b, b, a % b
        x, x1 = x1, x - q * x1
        y, y1 = y1, y - q * y1
    return a, x, y