def foo(a, b):
	if a == 0:
		return b, 0, 1
	g, x1, y1 = foo(b % a, a)
	x = y1 - (b // a) * x1
	y = x1
	return g, x, y