def euclid(a, b):
    """Solve x*a + y*b = ggt(a, b) and return (x, y, ggt(a, b))"""
    x = yy = 0
    y = xx = 1
    while b:
        q = a // b
        a, b = b, a % b
        x, xx = xx - q * x, x
        y, yy = yy - q * y, y
    return xx, yy, a
