from typing import Tuple


def egcd(a: int, b: int)->Tuple[int, int, int]:
    """Extended Euclidean algorithm to compute the gcd
    Taken from https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
    Returns:
        A tuple (g, x, y) where a*x + b*y = gcd(x, y)"""
    if a == 0:
        return (b, 0, 1)
    g, x, y = egcd(b % a, a)
    return (g, y - (b // a) * x, x)