def xgcd(a,b) :
  """Return g,c,d where g=ca+db is the gcd of a and b"""
  c,d,e,f = 1,0,0,1;
  while b :
    q,r= divmod(a,b);
    a,c,d,b,e,f = b,e,f,r,c-q*e,d-q*f;
  return (-a,-c,-d) if a < 0 else (a,c,d);