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 3^x (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