시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 32 13 11 57.895%

문제

Write a program that takes a natural number N and decomposes it as a sum of the minimum number of exact natural cubes. The program should find m1, m2, …, mk, such that each mi is a natural number, m13 +m23 +… +mk3 = N, and k is minimal.

입력

The only line of the input file contains the number N (1 ≤ N ≤ 44,777,444).

출력

Your program should write exactly two lines. The first line contains the number k - the minimum number of natural cubes. The second line contains k space-separated natural numbers - that raised to the power of 3 sum to N.

예제 입력 1

42

예제 출력 1

7
2 2 2 2 2 1 1

예제 입력 2

43

예제 출력 2

3
3 2 2