import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;public class VQC { static BigInteger zero = BigInteger.ZERO; static BigInteger one = BigInteger.ONE; static BigInteger two = BigInteger.valueOf(2); public static void main(String[] args) { Scanner s = new Scanner(System.in); for (;;) { BigInteger c = new BigInteger(s.next()); BigInteger d = sqrt(c); BigInteger e = c.subtract(d.pow(2)); BigInteger N = c.add(one).divide(two).subtract(d); BigInteger X = d.subtract(one); BigInteger T = evalT(X, c.subtract(d.pow(2))); Element c1 = getElement(e, N, T); System.out.println(c1); System.out.println(factor(c1) + "\n"); } } static Element factor(Element v) { Element mirror = v; for (;;) { mirror = mirror(mirror); System.out.println(mirror); BigInteger xpn2 = mirror.e.abs(); if (isSquare(xpn2)) { return getNontrivialElement(v, xpn2); } } } static Element getElement(BigInteger e, BigInteger n, BigInteger t) { BigInteger subtrahend = one; Element v = new Element(); v.e = e; v.n = n; v.t = t; try { if ((v.e.and(one)).equals(zero)) subtrahend = two; v.x = two.multiply(v.t).subtract(subtrahend); v.a = (v.x.pow(2)).add(v.e).divide(two.multiply(v.n)); v.d = v.a.add(v.x); v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n)); v.c = v.a.multiply(v.b); v.f = two.multiply(v.d).add(one).subtract(v.e); } catch (ArithmeticException ae) {} return v; } static Element getNontrivialElement(Element v, BigInteger xpn2) { BigInteger dpn2 = v.c.add(xpn2); BigInteger dpn = sqrt(dpn2); BigInteger n = dpn.subtract(v.d); BigInteger xpn = sqrt(xpn2); BigInteger x = xpn.subtract(n); BigInteger t = evalT(x, v.e); return getElement(v.e, n, t); } static Element mirror(Element v) { Element v2 = new Element(); v2.e = v.f.negate(); v2.n = v.n.subtract(one); v2.d = v.d.add(one); v2.x = v.x.add(one); BigInteger i = v2.d.add(v2.n); BigInteger j = v2.x.add(v2.n); v2.a = i.subtract(j); v2.b = i.add(j); v2.c = v2.a.multiply(v2.b); v2.f = v.d.add(one).pow(2).subtract(v.c); evalT(v2); return v2; } static void evalT(Element v) { BigInteger addend = one; if (v.e.and(one).equals(zero)) addend = two; v.t = v.x.add(addend).divide(two); } static BigInteger evalT(BigInteger x, BigInteger e) { BigInteger addend = one; if (e.and(one).equals(zero)) addend = two; return x.add(addend).divide(two); } static boolean gt(BigInteger i, BigInteger i2) { return i.compareTo(i2) 0; } static boolean gteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) >= 0; } static boolean lt(BigInteger i, BigInteger i2) { return i.compareTo(i2) < 0; } static boolean isSquare(BigInteger c) { return sqrt(c).pow(2).equals(c); } static BigInteger sqrt(BigInteger n) { if (n.equals(zero)) return zero; if (gt(n, zero)) { BigInteger root = one.shiftLeft(n.bitLength() >> 1); while (!isSqrt(n, root)) { root = root.add(n.divide(root)); root = root.shiftRight(1); } return root; } throw new ArithmeticException("Complex result"); } static boolean isSqrt(BigInteger n, BigInteger root) { return gteq(n, root.pow(2)) && lt(n, root.add(one).pow(2)); } static class Element { public BigInteger a, b, c, d, e, f, i, j, n, t, x; public Element() {} public String toString() { return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "}" + " " + getCoordinates(); } public void printFactors() { System.out.println("a = " + a); System.out.println("b = " + b); } public String getCoordinates() { return "(" + this.e + ", " + this.n + ", " + this.t + ")"; } }}