English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Sum of cubes

It is known that any natural number can be represented as the sum of no more than four squares of natural numbers. Vasya decided to come up with a similar statement for cubes - he wants to find out how many cubes are enough to represent any number. His first working hypothesis is eight.

It turned out that almost all the numbers that Vasya could come up with are represented as the sum of no more than eight cubes. However, the number 239, for example, does not allow such a representation. Now Vasya wants to find some other such numbers, as well as, perhaps, some regularity in the representations of all the other numbers, in order to put forward a hypothesis about the type of all numbers that are not represented as the sum of eight cubes.

Help Vasya write a program that would check whether it is possible to represent a given natural number as the sum of no more than eight cubes of natural numbers, and if possible, would find some such representation.

Input data

The natural number N <= 2*10 9 is entered.

Output data

It is required to output no more than eight natural numbers, the cubes of which add up to N. If the desired representation does not exist, then the word IMPOSSIBLE must be output to the output file.

Examples
Input data
239
Output data
IMPOSSIBLE
Input data
17
Output data
2 2 1

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)