Balanced Scale Challenge

You are given a balanced scale, a set of weights and an object. The available weights are powers of 3, i.e. 1, 3, 9, 27, 81, … In other words, for each nonnegative integer \(k\) there is exactly one weight of \(3^k\). You are provided a positive integer \(m\) representing the weight of an object. Your task is to place the object on the left pan of the scale and then arrange some of the available weights on either or both pans so that the scale is balanced.

The idea is to represent the number \(m\) in balanced ternary form (using digits -1, 0, and 1). In this representation, a digit of 1 indicates that the corresponding weight (\(3^k\)) should be placed on the right pan, while a digit of -1 indicates that it should be placed on the left pan (with the object). A digit of 0 means that the corresponding weight is not used.

Output the weights to be placed on each pan. If no weight is to be placed on a pan, output 0 for that pan.

inputFormat

The input consists of a single line containing a positive integer \(m\) (\(1 \le m \le 10^9\)).

outputFormat

Output two lines. The first line contains the weights (in ascending order) to be placed on the left pan (besides the object). The second line contains the weights (in ascending order) to be placed on the right pan. If a pan has no additional weight, output 0 for that line.

sample

2

1
3