public class GaussianInteger {
    int real, imag;

    public GaussianInteger(int a, int b) {
	real = a;  imag = b;
    }

    public GaussianInteger conjugate() {
	return new GaussianInteger(real, -imag);
    }

    public String toString() {
	return real + " + " + imag + " i";
    }

    public static final GaussianInteger ZERO = new GaussianInteger(0, 0);
    public static GaussianInteger multiply(GaussianInteger gi1,
					   GaussianInteger gi2) {
	return new GaussianInteger(gi1.real*gi2.real - gi1.imag*gi2.imag,
				   gi1.real*gi2.imag + gi1.imag*gi2.real);
    }

    public GaussianInteger minus(GaussianInteger b) {
	return new GaussianInteger(real - b.real, imag - b.imag);
    }

    public GaussianInteger times(GaussianInteger b) {
	return GaussianInteger.multiply(this, b);
    }

    public boolean isZero() {
	return (real == 0) && (imag == 0);
    }

    public GaussianInteger[] dividedBy(GaussianInteger b) {
	double den = b.real*b.real + b.imag*b.imag;
	double bInverseReal = b.real/den;
	double bInverseImag = -b.imag/den;
	double quotientReal = real*bInverseReal - imag*bInverseImag;
	double quotientImag = real*bInverseImag + imag*bInverseReal;
	GaussianInteger[] result = new GaussianInteger[2];
	result[0] = new GaussianInteger((int) Math.round(quotientReal),
					(int) Math.round(quotientImag));
	result[1] = minus(b.times(result[0]));
	return result;
    }

    public GaussianInteger remainderWhenDividedBy(GaussianInteger b) {
	GaussianInteger[] r = dividedBy(b);
	return r[1];
    }

    public static GaussianInteger gcd(GaussianInteger a, GaussianInteger b) {
	GaussianInteger m = a;
	GaussianInteger n = b;
	while(!n.isZero()) {
	    GaussianInteger r = m.remainderWhenDividedBy(n);
	    m = n;
	    n = r;
	}
	return m;
    }

}