from typing import Tuple


def extgcd(a: int, b: int) -> Tuple[int, int, int]:
    """a * x + b * y = gcd(a, b)

    See:
    https://qiita.com/drken/items/b97ff231e43bce50199a
    https://www.youtube.com/watch?v=hY2FicqnAcc

    O(gcd(a, b))
    """

    if b == 0:
        return (a, 1, 0)

    g, x, y = extgcd(b, a % b)

    return g, y, x - (a // b) * y