Jacobi Numbers

문제

Today, a new paper has been published in the Bulletin of Apocryphal Pioneers in Computation. According to this paper, the forgotten German number theorist Wahnfried Imaginus Jacobi (1806--1853), while still a secondary student in Potsdam, investigated the decomposition of integers into sums of cubes. Among the examples noted in the surviving fragments of his notebooks are \[ 2025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3 \] and the more curious expression \[ 3 = 1^3 + 1^3 + 1^3 = 4^3 + 4^3 + (-5)^3\,,\] which shows that a solution need not be unique. Jacobi restricted his attention to small integers and probably did not know the decomposition \[ 3 = 569\,936\,821\,221\,962\,380\,720^3 + (-569\,936\,821\,113\,563\,493\,509)^3 + (-472\,715\,493\,453\,327\,032)^3 \,,\] which was discovered only recently.¹ However, Jacobi did manage to prove that a decomposition into cubes always exists for all positive integers up to $92419241$, the $2828$th cuban prime of the first kind. Although his work was never published, references to the method appear in a marginal annotation in an 1823 letter to his famous brother Carl Gustav Jacob.

Given a positive integer $nn$, output a list of at most $1000010\backslash ,000$ integers between $-10000-10\backslash ,000$ and $1000010\backslash ,000$ such that the sum of their cubes equals $nn$.

¹Booker, Andrew R.; Sutherland, Andrew V. (2021), "On a question of Mordell", Proceedings of the National Academy of Sciences, 118 (11)

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 92411\backslash leq\; n\backslash leq\; 9241$), the number to decompose into cubes.

출력

Output an integer $kk$ ($1\le k\le 100001\; \backslash leq\; k\; \backslash leq\; 10\backslash ,000$), the number of terms in your solution, followed by $kk$ integers $a_1,\dots ,a_{k}a\_1,\backslash ldots,\; a\_k$ ($-10000\le a_i\le 10000-10\backslash ,000\backslash leq\; a\_i\backslash leq10\backslash ,000$ for each $ii$), such that $a_1^3+\cdots +a_k^3=na\_1^3\; +\; \backslash dots\; +\; a\_k^3\; =\; n$.

If there are multiple valid solutions, you may output any one of them.