Thăng bằng cân

Cửa hàng của duyhung123abc có một cái cân và các quả cân có khối lượng có dạng 3k (tức lũy thừa của 3). VD: 1, 3, 9, 27, 81, ...

Khối lượng của các quả cân khác nhau từng đôi một. Duyhung123abc có một vật nặng M kg, vật nặng được đặt vào đĩa bên trái của cái cân. Hãy giúp anh ta đặt các quả cân vào 2 đĩa sao cho cân thãng bằng
Input

- Chứa 1 số nguyên M duy nhất (0 <= M <= 100 000 000)
Output

- Kết quả gồm 2 dòng

- Dòng 1: số A là số quả cân đặt vào đĩa bên trái, theo sau gồm A số là khối lượng của các quả cân theo thứ tự tăng dần

- Dòng 2: số B là số quả cân đặt vào đĩa bên phải, theo sau gồm B số là khối lượng của các quả cân theo thứ tự tăng dần
Example

Input:
42

Output:
3 3 9 27
1 81

Tham lam là ok.

Bài này không cần tham làm chỉ cần quan tâm phân tích một số ra hệ cơ số 3 thôi.
Bạn nghĩ tiếp đi!

Cách chi lạ rứa ^^. Anh nói thủ đi. Em tham khảo. ^^

Cái này bạn suy nghĩ đi nha! Nghĩ một chút là ra mà! Nếu tìm được bên trái sẽ tìm được bên phải!

Phân tích bên trái ra hệ cơ số 3. Tìm một số nhỏ nhất lớn hơn hoặc bằng số vừa phân tích và có các chữ số là 0 hoặc 1. ???