import java.math.*;
public class BGCD{
 public static void main (String[] args) 
{ BigInteger S, P, Q, R;
  S = new BigInteger("110081");
  P = new BigInteger("34567");  P = P.multiply(S);
  Q = new BigInteger("56789");  Q = Q.multiply(S);
  R = BGCD(P, Q);
  System.out.println("P="+P.toString()+" Q="+Q.toString());
  System.out.println("gcd(P,Q)="+R.toString()); 
}
//=====================================C
 public static BigInteger BGCD(BigInteger P, BigInteger Q)
{ BigInteger Zero = new BigInteger("0");
  if(Q.compareTo(Zero) == 0) return P;
  return BGCD(Q, P.mod(Q));  }
}