def bezout(a,b):
    if b==0:
        return (a,1,0)
    (d,x,y) = bezout(b,a%b)
    (x,y) = (y,x-a//b*y)
    assert a*x+b*y==d
    return (d,x,y)