LL gcd(LL a, LL b)
{
	while(a)
		swap(a, b%=a);
	return b;
}

LL lcm(LL a, LL b)
{
	return a/gcd(a,b)*b;
}

// Assumption: (a/b)*b+(a%b) == a
//   For typical C/C++ compilers, % on negatives satisfies this.
//   To be sure, replace a%b by a-a/b*b

LL xgcd(LL a, LL b, LL* x, LL* y) // ax+by=g
{
	if(b) {
		LL yy, g = xgcd(b,a%b,&yy,x);
		*y = yy - a/b**x;
		return g;
	}
	else {
		*x=1, *y=0;
		return a;
	}
}
