from typing import Tuple


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

    :param a: integer
    :param b: integer
    :return: The gcd of a and b, and x and y such that ax + by = gcd(a, b)
    """
    if a == 0 and b == 0:
        return 0, 0, 0

    equation1 = [1, 0, a]
    equation2 = [0, 1, b]

    # when we divide y by x, we say y = qx + r

    while True:
        if equation1[2] == 0:
            if equation2[2] > 0:
                return equation2[2], equation2[0], equation2[1]
            else:
                return -equation2[2], -equation2[0], -equation2[1]

        q = equation2[2] // equation1[2]
        equation2 = [equation2[index] - q * equation1[index] for index in range(3)]

        if equation2[2] == 0:
            if equation1[2] > 0:
                return equation1[2], equation1[0], equation1[1]
            else:
                return -equation1[2], -equation1[0], -equation1[1]

        q = equation1[2] // equation2[2]
        equation1 = [equation1[index] - q * equation2[index] for index in range(3)]