J. Something that resembles Waring's problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Waring's problem is a number-theoretic statement, according to which for every integer $$$n \gt 1$$$ there exists a number $$$k=k(n)$$$ such that any natural number $$$N$$$ can be represented as: $$$$$$x_1^n + x_2^n + ... + x_k^n = N$$$$$$ with non-negative integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$.

You are required to represent the number $$$x$$$ in the form of $$$a_1^3 + a_2^3 + ... + a_k^3 = x$$$, with integers $$$a_1$$$, ..., $$$a_k$$$ and $$$k \le 5$$$.

Input

The first line contains the number $$$x$$$ $$$(1 \le x \le 10^{100000})$$$.

Output

If such a representation does not exist, type $$$-1$$$. Otherwise, in the first line, type the number $$$k$$$ — the number of numbers. In the second line, type $$$k$$$ integers $$$a_i$$$ $$$(|a_i| \le 10^{110000})$$$.

Examples
Input
5
Output
5
1 1 1 1 1
Input
17
Output
3
1 2 2
Note

In the first example: $$$1^3 + 1^3 + 1^3 + 1^3 + 1^3 = 5$$$.

In the second example: $$$1^3 + 2^3 + 2^3 = 17$$$.