Cần cân vật nặng ~N~ gram bằng các quả cân có khối lượng ~3^k~ gram, mỗi loại đúng một quả. Vật đặt ở đĩa trái; có thể đặt thêm quả cân vào cả hai đĩa sao cho cân thăng bằng và dùng ít quả cân nhất.

Input

Một số tự nhiên ~N~ ~(1 < N < 10^{10})~.

Output

Dòng 1: số quả cân thêm vào đĩa trái, sau đó là khối lượng các quả cân đó.

Dòng 2: số quả cân đặt vào đĩa phải, sau đó là khối lượng các quả cân đó.

Bộ test gồm 50 testcase, có test biên và test ngẫu nhiên theo giới hạn đề.

Subtask

• 100% s? ?i?m: ~1 < N < 10^{10}~.