// goodwincommaderek@gmail.com import java.io.IOException; import java.util.ArrayList; import java.util.Scanner; public class ac_dg { // a number R can be written as // R = a*a + b*b // for integer a and b IF AND ONLY IF // no prime in R's prime factorization has an odd exponent, if said prime is congruent to 3 under mod 4 // so, idea: // find an (N - c*c) = R that satisfies the above criteria // and then find a and b (and we're guaranteed to have a,b,c once we find an R that works) // but we'll have to speed up our finding of c // let's use a sieve to do that! // the sieve will generate, for a range of numbers, // the part of an integer that's just the "harmless" part of its prime factorization, // and the part of an integer which is harmful (product of all p^k where k is odd and p % 4 == 3). // note that for a large enough sieve, in theory, N = harmful[N]*harmless[N]. // in practice, if our sieve considers primes up to M, then if N is <= M^2, // then N has at most one prime in its factorization which is greater than M, whose exponent is 1. // if it did, it would equal N / harmful[N]*harmless[N]. // we can easily check to see whether it's harmful or harmless. // so, we can use the sieve to find whether a number in said sieve's range is usable in O(1). // note that this code is only assumed to work if the smallest integer of the triplet is small(ish). // because Ns divisible by 4^k for positive k tend to be the ones which break this idea the hardest, // and 4N = (2a)^2 + (2b)^2 + (2c)^2, // we can simply divide by 4 as many times as we need to, solve the problem, // and then multiply a, b, and c by 2 as many times as we divided N by 4 to avoid this. static long INCREMENT = 1_000_000L; static boolean DEBUG = false; static void debug(String msg) { if (DEBUG) System.out.println(msg); } static boolean isPossible(long N) { for(long forbiddenRemainder = 7, mod = 8; forbiddenRemainder <= N; forbiddenRemainder *= 4, mod *= 4) { if (N % mod == forbiddenRemainder) { return false; } } return true; } static ArrayList primes; static void static_precomp(int upToNotIncluding){ boolean[] isNotPrime = new boolean[upToNotIncluding]; isNotPrime[0] = isNotPrime[1] = true; primes = new ArrayList<>(); for(int p = 2; p < upToNotIncluding; p++) { if (!isNotPrime[p]) { for(int pk = p+p; pk < upToNotIncluding; pk += p) { isNotPrime[pk] = true; } primes.add(p); } } debug("static precomp ended"); } static long[][] sieveHarmlessAndHarmfulPrimeDivisor(long lowerInclusive, long upperExclusive) { int size = (int) (upperExclusive - lowerInclusive); long[] harmlessPrimeDivisors = new long[size]; long[] harmfulPrimeDivisors = new long[size]; for (int i = 0; i < size; i++){ harmlessPrimeDivisors[i] = harmfulPrimeDivisors[i] = 1; } // amortized O(size * log(size)) for(Integer pobj : primes) { long p = pobj.intValue(); boolean isSquare = false; boolean isForbidden = p % 4 == 3; for(long pPow = p; pPow < 1_000_000_000_000L; pPow *= p, isSquare = !isSquare) { // find the first spot from which to sieve for this pPow long start = lowerInclusive - (lowerInclusive % pPow); if (start < lowerInclusive) start += pPow; if (start >= upperExclusive) break; int intPPow = (int) pPow; if (!isForbidden) { // harmless for(int i = (int)(start - lowerInclusive); i < size; i += intPPow) { harmlessPrimeDivisors[i] *= p; if (pPow > size) break; } } else { // either harmful or harmless, depending on whether p is a square long[] undoHere = isSquare ? harmfulPrimeDivisors: harmlessPrimeDivisors; long[] putHere = isSquare ? harmlessPrimeDivisors: harmfulPrimeDivisors; long pPowPrev = pPow / p; for(int i = (int)(start - lowerInclusive); i < size; i += intPPow) { undoHere[i] /= pPowPrev; putHere[i] *= pPow; if (pPow > size) break; } } } } return new long[][]{harmlessPrimeDivisors, harmfulPrimeDivisors}; } static long[] findTwinSquaresBruteForce(long N) { for (long a = 0; a*a <= N; a++) { long btimesb = N - a*a; long b = (long) Math.sqrt(btimesb); if (b*b + a*a == N) { return new long[]{a,b}; } } return null; } static long[] solve(long N) { // wait! before we do this // let's check if it's possible if (!isPossible(N)) { return null; } // ok. proceed the sieve long upperExcl = N+1, lowerIncl = N+1 - INCREMENT; long c = 0; while (upperExcl > 0) { lowerIncl = Math.max(lowerIncl, 0); while (N - c*c >= upperExcl) { c++; debug("c is now "+c); } if (N - c*c < lowerIncl) { continue; } debug("sieve starting ..."); long[][] sieve = sieveHarmlessAndHarmfulPrimeDivisor(lowerIncl, upperExcl); debug("sieve ended"); while (N - c*c >= lowerIncl) { int index = (int) ((N - c*c) - lowerIncl); long res = (N - c*c) / sieve[0][index]; debug(N+" "+sieve[0][index]+" "+res); boolean foundValidC = false; if (res == 1) { // PF of N-c*c only consists of small harmless numbers. foundValidC = true; } else if (res % 4 != 3) { // N-c*c doesn't get here if its PF has one very big harmful prime // but it could still have harmful small primes and one big harmless prime, so let's check for that if (sieve[1][index] == 1) { foundValidC = true; } } if (foundValidC) { debug("N-c*c of "+(N-c*c)+" worked!"); // found a valid c!!!! long[] a_and_b = findTwinSquaresBruteForce(N - c*c); return new long[]{a_and_b[0], a_and_b[1], c}; } // ... c++; debug("c is now "+c); } debug("sieve found nothing yet...?"); // found nothing yet ... upperExcl = lowerIncl; lowerIncl -= INCREMENT; } debug("we should never get here"); return null; } // multiples of 4^k for large k often break this solution, so let's add a wrapper static long[] solveWrapper(long N) { int numTimesDivBy4 = 0; while (N % 4 == 0) { numTimesDivBy4++; N /= 4; } long[] ans = solve(N); if (ans == null) return null; while (numTimesDivBy4 > 0) { numTimesDivBy4--; for (int i = 0; i < 3; i++) { ans[i] *= 2; } } return ans; } public static void main(String[] args) throws IOException { // generate primes static_precomp((int) (INCREMENT+1)); Scanner in = new Scanner(System.in); for (int i = 1; i < 2; i++) { long N = in.nextLong(); long[] ans = solveWrapper(N); if (ans == null) { System.out.println(-1); } else { System.out.println(ans[0]+" "+ans[1]+" "+ans[2]); if (ans[0]*ans[0] + ans[1]*ans[1] + ans[2]*ans[2] != N) { debug("WRONG"); } } } } }