#include<fstream.h>
ifstream f("euclid.in");
ofstream g("euclid.out");
void euclid(int a,int b,int *d,int*x,int *y)
{
	if(b==0)
	{*d=a;
	*x=1;
	*y=0;
	}
	else
	{
	int x0,y0;
	euclid(b,a%b,d,&x0,&y0);
	*x=y0;
	*y=x0-(a/b)*y0;
	}
}