long long nod1(long long a, long long b)
{
 	if (b == 0)
	{
		return a;
	}
	else
	{
		if (a == 0)
		{
			return b;
		}
		else
		{
			int d = nod1(b, a%b);
			return d;
		}
	}
}
long long nod1(long long a, long long b,long long&x,long long&y)
{
 	if (b == 0)
	{
		x = 1;
		y = 1;
		return a;
	}
	else
	{
		if (a == 0)
		{
			x = 1;
			y = 1;
			return b;
		}
		else
		{
			long long x1, y1;
			long long d = nod1(b, a%b,x1,y1);
			x = y1;
			y = x1 - a / b*y1;
			return d;
		}
	}
}