Description

You are given a balanced beam scale, a set of weights, and an object. The weights are $1, 3, 9, 27, 81, \dots$, that is, each weight is a power of $3$, and for every integer $k \ge 0$ there is exactly one weight of mass $3^k$. The object has mass $m$, where $m$ is a positive integer. Your task is to place the object on the left pan, and then place some of the weights on the left pan, the right pan, or both, so that the scale is balanced.

Input Format

The first line contains an integer $m$.

Output Format

The first line contains information about the weights placed on the left pan. The first number must be a non-negative integer, the number of weights placed on the left pan, followed by the weights’ masses in increasing order. The numbers must be separated by a single space. The second line contains information about the weights placed on the right pan in the same format as the first line.

42

3 3 9 27
1 81

30

0
2 3 27

Hint

Constraints

For $100\%$ of the testdata, $1 \le m \le 10^{100}$.

Notes

From Day 1:SCALES of Baltic Olympiad in Informatics 2004.

Translated and organized by @求学的企鹅.

Translated by ChatGPT 5