22217번 - Scales 다국어

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 ≥ 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.

The first line contains one integer m, 1 ≤ m ≤ 10¹⁰⁰.

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.