def extended_gcd(a, b):
    """Find the solution of ax + by = gcd(x, y), returns (x, y, gcd(x, y))"""
    if b == 0:
        return 1, 0, a
    x, y, gcd = extended_gcd(b, a % b)
    return y, x - (a // b) * y, gcd