You are given an integer M. You have an infinite collection of weights, where each weight is a distinct power of 3 (3^0, 3^1, 3^2, \dots). There is exactly one weight available for each power.
Your task is to place the weight M on the left side of a scale and then distribute some of the available weights from your collection between the left and right sides so that the scale is perfectly balanced. Each power of 3 can be used at most once (placed on the left side or the right side).
Input
The input contains a single integer M (1 \le M \le 10^{12}).
Output
On the first line, print the number of weights placed on the left side (excluding M), followed by the values of those weights in increasing order.
On the second line, print the number of weights placed on the right side, followed by the values of those weights in increasing order.
If there are multiple valid configurations, you can output any of them.
Examples
| standard input | standard output |
|---|
| 2
| 1 1
1 3
|
| 7
| 1 3
2 1 9
|