def ext_euclid(a, b):
    """Use extended Euclid algorithm to find gcd of a and b, along with
    the coefficients of Bezout's identity, a*x + b*y = gcd(a, b)
    The tuple(gcd(a, b), x, y) is returned.
    """
    assert a > 0 and b > 0
    reverse = b > a
    if reverse:
        r0, s0, t0 = b, 1, 0
        r1, s1, t1 = a, 0, 1
    else:
        r0, s0, t0 = a, 1, 0
        r1, s1, t1 = b, 0, 1
    while r1 > 0:
        q = r0 // r1
        r2, s2, t2 = r0 - q*r1, s0 - q*s1, t0 - q*t1
        r0, s0, t0 = r1, s1, t1
        r1, s1, t1 = r2, s2, t2
    if reverse:
        return r0, t0, s0
    return r0, s0, t0