Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2759
Perfect Weighing Skill

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Michael is interested in physics. During his playing with balances and counterpoises, he finds that if he chooses a set of suitable counterpoises, he can weigh many more different weights than others. After a series of hard work, Michael decides to choose the counterpoises which have the weight 1,3,9,27,....,exactly all the power exponents of 3. He thinks he can weigh every weight with these counterpoises. But Alex is doubt about this. He says he can give an object which cannot be weighed by this set of counterpoises. Now Michael is asking for your help to win the bet. He also tells you a secret to help: "The counterpoises could be placed on both sides of the balance. As well, the weight of all Alex's objects are no more than integers. Cheer up! You'll win."


Input

The input consists of multiple test cases. Each case contains a single integer M, 1<=M<=500000000, which represents the weight of Alex's object to be weighed by the balance.


Output

For each test case, output 2 lines. The first line is the counterpoises which should be put at the same side of the object. If there are none, output -1.The second line is the counterpoises which should be put at the different side of the object. If there are none, output -1.If the object cannot be weight, you should output -1 only in both line. An empty line should be printed after each test case.


Sample Input

13
35


Sample Output

-1
1 3 9

1
9 27


Author: JI, Cheng
Source: ZOJ Monthly, September 2006
Submit    Status