#include<fstream.h>
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
//int euclidex(int a,int b,in &x,int&y)
{
    int r,q,x,x1,x2,y,y1,y2;
    if(b==0){x=1;y=o;return a;}
        else{x1=1;y1=0
             x2=0;y2=1
             r=x%b;q=a/b;
             while(r)
                {x=x1-x2*q;x1=x2;x2=x;
                 y=y1-y2*q;y1=y2;y2=y;
                 a=b;b=r;r=a%b;q=a/b
                }
             return b;

    }
    fout.close(); return 0;

}