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 \(3k\) (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 \le M \le 10^8\))

Output

• 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

42 

3 3 9 27
 1 81