세제곱수의 합

자연수 $N$이 주어진다. $N$을 자연수의 세제곱 합으로 나타내되 항의 개수를 가장 적게 하려고 한다. 즉,

$m_1^3 + m_2^3 + \cdots + m_k^3 = N$

을 만족하는 자연수 $m_1, m_2, \ldots, m_k$를 찾고, 이때 $k$를 최소로 한다. 같은 수를 여러 번 써도 된다.

첫째 줄에 자연수 $N$이 주어진다. ($1 \le N \le 44{,}777{,}444$)

두 줄을 출력한다. 첫째 줄에는 세제곱 항의 최소 개수 $k$를 출력한다. 둘째 줄에는 세제곱해서 더하면 $N$이 되는 자연수 $k$개를 공백 하나로 구분해 출력하며, 앞의 수가 뒤의 수보다 작지 않도록 정렬한다.

항이 $k$개인 조합이 여러 가지면 사전순으로 가장 앞서는 것을 출력한다. 두 조합을 앞에서부터 비교해 처음으로 달라지는 자리에 더 작은 수가 있는 쪽이 앞선다. 예를 들어 $N = 1729$는 $12^3 + 1^3$과 $10^3 + 9^3$ 모두 세제곱 두 개로 나타내므로 답은 10 9이다.