Giải bài trực tuyế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 3^k (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