QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB
[0]

# 9706. The Answer to the Ultimate Question of Life, The Universe, and Everything.

Statistics

For decades, scientists have wondered whether each of the numbers from 0 to 100 could be represented as the sum of three cubes, where a cube is the same number multiplied together three times.

42 was the last number without a proven solution — until now.

The solution is (80538738812075974)3+804357581458175153+126021232973356313=42

Now, Yen-Jen is suspicious of the existence of other solutions. But, the solutions are not so trivial to find out. Yen-Jen wants to find out easy solutions first. That is, for the equation a3+b3+c3=x, Yen-Jen wants to find out at least one solution for each integer x in [0,200], where |a|,|b|,|c|5000.

Since Yen-Jen is still busy preparing the test data of some(this?) problem, please help him find out at least one solution for each x or tell him that the solution doesn't exist when |a|,|b|,|c|5000.

Input

The first line contains an integer T indicating the number of x to be checked.

Following T lines each contains one integer x.

  • 1T10
  • 0x200

Output

For each test case, output one line containing three space-separated integers a,b,c such that a3+b3+c3=x and |a|,|b|,|c|5000. If the solution doesn't exist, output "impossible".

Sample Input

2
1
2

Sample Output

1 1 -1
1 1 0