from typing import Tuple


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

    Finds :code:`gcd(a,b)` along with coefficients :code:`x`, :code:`y` such that
    :code:`ax + by = gcd(a,b)`.

    Args:
        a: first number
        b: second number

    Returns:
        gcd(a,b), x, y
    """
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y