완전제곱수

수론의 유명한 정리에 따르면 모든 양의 정수는 네 개의 완전제곱수의 합으로 나타낼 수 있다. 하지만 보통은 더 적은 개수의 제곱수로 충분하다. 예를 들어 $27$은 세 개의 완전제곱수만으로 나타낼 수 있다: $27 = 5^2 + 1^2 + 1^2$.

수학자 친구가 완전제곱수에 관한 다음 사실들을 알려 준다.

• 홀수 소수 $p$가 두 제곱수의 합으로 나타나는 것은 $p \equiv 1 \pmod 4$일 때이고 그때에만 해당한다.
• 두 양의 정수 $a$와 $b$가 각각 두 제곱수의 합으로 나타나면, 그 곱 $ab$도 두 제곱수의 합으로 나타난다.
• 모든 양의 정수는 세 개의 완전제곱수의 합으로 나타낼 수 있다. 다만 $4^a \cdot (8b + 7)$ 꼴인 수는 제외한다. 여기서 $a$와 $b$는 음이 아닌 정수이다.

세 제곱수의 합에 관한 마지막 사실이 흥미로워서, 이 주장이 참인지 확인하고 실제 제곱수를 구하는 프로그램을 작성하려 한다.

정수 $n$ ($1 ≤ n ≤ 10^{12}$) 하나가 주어진다.

$n$을 세 제곱수의 합으로 나타낼 수 있으면 세 정수 $x$, $y$, $z$를 출력한다. $0 ≤ x, y, z ≤ \sqrt{n}$이고 $n = x^2 + y^2 + z^2$이면 정답으로 인정한다. 조건을 만족하는 $x$, $y$, $z$의 조합이 여러 개이면 그중 아무것이나 출력해도 된다. $n$이 두 개 이하의 제곱수 합으로만 나타나더라도 반드시 정확히 세 정수를 출력한다. $n$을 세 제곱수의 합으로 나타낼 수 없으면 $-1$을 출력하고 다른 값은 출력하지 않는다.