def xgcd(A, B):
    """
    Finds g=gcd(A,B) and solves the equation A*n+B*m=gcd(A,B).  Returns g, n, m.
    """
    a, b = A, B
    n1, m1, n, m = 0, 1, 1, 0
    if B == 0:
        return A, 1, 0
    r = b
    while r > 0:
        g = r
        q, r = divmod(a, b)
        n1, m1, n, m = n - q * n1, m - q * m1, n1, m1
        a, b = b, r
    return g, n, m
