def xgcd(a, b):
    """xgcd(a,b) returns a tuple of form (g,x,y), where g is gcd(a,b) and
	x,y satisfy the equation g = ax + by."""
    a1 = 1
    b1 = 0
    a2 = 0
    b2 = 1
    aneg = 1
    bneg = 1
    if a < 0:
        a = -a
        aneg = -1
    if b < 0:
        b = -b
        bneg = -1
    while 1:
        quot = -(a // b)
        a = a % b
        a1 = a1 + quot * a2
        b1 = b1 + quot * b2
        if a == 0:
            return b, a2 * aneg, b2 * bneg
        quot = -(b // a)
        b = b % a
        a2 = a2 + quot * a1
        b2 = b2 + quot * b1
        if b == 0:
            return a, a1 * aneg, b1 * bneg
