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