시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB68271435.000%

문제

재홍이는 자연수를 100,000 이하의 수밖에 알지 못한다. 하지만 친절한 종혁이는 재홍이에게 곱셈을 가르쳐 주었고, 이제 재홍이는 100,000 이하의 수들을 곱해서 만들 수 있는 자연수까지 알 수 있게 되었다.

어느 날 문득, 재홍이는 자신이 알고 있는 자연수를 최소 개수의 제곱수의 합으로 나타내 보고 싶다는 생각이 들었다. 그래서 자신이 원래 알고 있던 100,000 이하의 자연수들을 가지고 만들어 보았더니, 많아야 4개의 제곱수를 사용하면 모든 자연수를 제곱수의 합으로 나타낼 수 있다는 것을 알았다.

이제 재홍이는 종혁이에게 배워서 새로 알게 된 큰 수들도 네 개의 제곱수의 합으로 표현될 수 있는지를 알고 싶어졌다. 물론 네 개 이하의 제곱수로도 만들 수 있는 경우도 있겠지만, 편의를 위해 0 또한 제곱수로 보고 정확히 네 개의 제곱수의 합으로 나타내 보도록 하려고 한다.

재홍이가 알고 있는 자연수가 주어졌을 때, 이를 네 개의 제곱수의 합으로 표현하는 프로그램을 작성하시오. 반드시 최소 개수로 표현할 필요는 없다.

입력

첫째 줄에 N (1 ≤ N ≤ 1018)이 주어진다. 주어지는 N은 소인수가 모두 100,000 이하인 수이다.

출력

첫째 줄에 네 개의 음 아닌 정수 형태로 출력한다. 이 네 수를 제곱해서 더하면 반드시 N이 되어야 한다.

예제 입력 1

86

예제 출력 1

3 4 5 6