Scales

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3029
64-bit integer IO format: %I64d      Java class name: Main

Description

Give you a scale, a goods weigts m kilograms. And then give you some stones weighting 1, 3, 9, 27, ..., 3^k. Of course, the number of different weights' is only ONE.

Now put the goods on the left of scale. And then you should put some stones on two sides of scale to make the scale balanced.

Input

An integer m, stands for the weights of the goods (0 ≤ m ≤ 100 000 000)

Output

You should output two lines.

In the first line, the first integer N1 is the number of stones putting on the left of scale, and then N1 integers follow(in the ascend order), indicating the weight of stones putting on the left, seperated by one space. In the second line, please use the same way as the first line's to output the N2, which is the number of stones putting on the right side. Then following N2 integers, which are in ascending order, indicate the stones' weight putting on the right side.

Sample Input

42
30

Sample Output

3 3 9 27
1 81
0
2 3 27

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .