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 đó.

Subtask

• 100% số điểm: không có ràng buộc bổ sung ngoài các giới hạn đã nêu ở phần Input.

Ví dụ 1

69

2 3 9
1 81

Ví dụ 2

2

1 1
1 3