Scales

Time limit1sMemory limit512 MB

Summary

Given an object of weight m, choose distinct powers of 3 for each pan so that the object plus the left pieces balances the right pieces.

Level: Medium4 of 10
Topics: Math, Number theory, Greedy, Implementation
Solved: No attempts yet

Problem

You are given an equal arm scales, a set of weight pieces and an object. The pieces are of weight 1, 3, 9, 27, 81, ..., i.e. the weight of each piece is a power of 3, and for each integer $k \ge 0$ there is exactly one piece of weight $3^k$ . The object's weight is $m$ , where $m$ is a positive integer. Your task is to put the object on the left scale pan and to put some pieces on one or both scale pans, so that the scales is in balance.

Write a program that:

reads the object's weight $m$ from the input,
calculates which pieces should be put on the left and right scalepan,
writes the results to the output.

Input

The first line contains one integer $m$ , $1 \le m \le 10^{100}$ .

Output

The output should consist of two lines.

The first line should contain information about pieces put on the left scale pan. First number must be non-negative integer - number of pieces put on the left scale pan followed by weights of pieces in increasing order. Numbers must be separated by single spaces.

The second line must contain information about pieces put on the right scale pan in the same format as first line.

Examples2

Example 1
Input
```
42
```
Expected output
```
3 3 9 27
1 81
```
Example 2
Input
```
30
```
Expected output
```
0
2 3 27
```