

import java.awt.event.*;
import java.awt.*;

public class MathRational {
    public int p;  //numerator
     public int q;  //denominator
    public int code;
   public  int level;

    public MathRational(int p,int q) {
	this.p=p;
	this.q=q;
	this.code=0;
	this.level=0;
    }

    public MathRational() {}


    //first number should be bigger

    public static int[] euclideanAlgorithmStep(int[] E) {
	int[] G=new int[2];
	G[0]=E[1];
	G[1]=E[0]%E[1];
	return(G);
    }

    //reorder so that first number is bigger and both are nonnegative
    public static int greatestCommonDivisor(int a,int b) {
	int[] F=new int[2];
	int a2=a;
	int b2=b;
	if(a<0) a2=-a;
	if(b<0) b2=-b;
	if(a==0) return(1);
	if(b==0) return(1);
	if(a2==b2) return(1);
	int a3=a2;
	int b3=b2;
	if(a2<b2) {a3=b2;b3=a2;}
	//at this point a3 and b3 are positive and a3>b3
	F[0]=a3;
	F[1]=b3;
	while(F[1]>0)  F=euclideanAlgorithmStep(F);  
	return(F[0]);
    }

    public static MathRational reduce(MathRational F) {
	int k=greatestCommonDivisor(F.p,F.q);
	MathRational G=new MathRational(F.p/k,F.q/k);
	return(G);
    }


    public static int[] RMINUS(int a,int b) {

	int test=-1;
	for(int i=1;i<b;++i) {
	    if((i*a)%b==1) test=i;
	}
	int[] d=new int[2];
	d[1]=test;
	d[0]=test*a/b;
	return(d);
    }

    public static int[] RPLUS(int a,int b) {

	int test=-1;
	for(int i=1;i<b;++i) {
	    if((i*a)%b==b-1) test=i;
	}
	int[] d=new int[2];
	d[1]=test;
	d[0]=(test*a+1)/b;
	return(d);
    }


    public static int[] PREVIOUS(int a,int b) {
	int[] d1=RPLUS(a,b);
	int[] d2=RMINUS(a,b);
	int[] e=new int[2];
	e[0]=d1[0]-d2[0];
	e[1]=d1[1]-d2[1];
	if(e[0]<0) e[0]=-e[0];
	if(e[1]<0) e[1]=-e[1];
	return(e);
    }

    public static int diophantine(int a,int b) {
	int[] c=PREVIOUS(a,b);
	double A1=1.0*a/b;
	double A0=1.0*c[0]/c[1];
	double k=2.0/(c[1]*c[1]*Math.abs(A0-A1));
	int kk=(int)(Math.floor(k));
	return(kk);
    }

    public static int[] superior(int a,int b) {
	int test=0;
	int[] c=new int[2];
	c[0]=a;
	c[1]=b;
	while(test==0) {
	    int k=diophantine(c[0],c[1]);
	    if(k>1) test=1;
	    if(b==1) test=1;
	    c=PREVIOUS(c[0],c[1]);
	}
	return(c);
    }


    public static int[] computeModular(int aa,int bb,int p,int q,int n) {

	int a=aa;
	int b=bb;
	if(a>b) a=a%b;

	int[] dd=RPLUS(a,b);
	int c=dd[0];
	int d=dd[1];

	int[] u=new int[2];
	u[0]=a*p+c*q+a*n*q;
	u[1]=b*p+d*q+b*n*q;

	int div=MathRational.greatestCommonDivisor(u[0],u[1]);
	u[0]=u[0]/div;
	u[1]=u[1]/div;
	return(u);
    }



}
