Baltic Olympiad in Informatics: 2004 Day 1, Problem 2

You are given an equal arm scale, a set of weight pieces, and an object. The pieces are of weight ~1, 3, 9, 27, 81, \dots~, 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 scale is in balance.

Constraints

~1 \le m \le 10^{100}~

Input Specification

The first line of the input contains one integer ~m~.

Output Specification

Your output should consist of two lines.

The first line should contain information about pieces put on the left scale pan. The first number must be a non-negative integer - the 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 with the same format as the first line.

Sample Input 1

42

Sample Output 1

3 3 9 27
1 81

Sample Input 2

30

Sample Output 2

0
2 3 27